b_수레움직이기_250134

문제

답

따라갈때문제가생김 무적건빨간색 먼저 움직이는 로직임.

"""
n*m크기
시작>도착
각턴마다 상하좌우중인접한 한칸으로 움직여야함
방문햇던곳갈수없음
도착시 고정
수레끼리 자라바꿀수없음(부딪히면안됨)
dfs같은데용?
"""
import math
import traceback

def solution(maze):
    answer = [math.inf,len(maze)*len(maze[0])]# 빈칸 0 / 방문 빨,파 1,2/ 
    def goBox(red_pos,blu_pos,red_dep,blu_dep,red_fin,blu_fin):
        # print(red_pos,blu_pos,red_dep,blu_dep,red_fin,blu_fin)
        turn = max(red_dep,blu_dep)
        red_clear = red_pos[0] <mark> red_fin[0] and red_pos[1] </mark> red_fin[1]
        blu_clear = blu_pos[0] <mark> blu_fin[0] and blu_pos[1] </mark> blu_fin[1]
        if turn>answer[1]:
            return
        if red_clear and blu_clear:
            # print("도착!",red_pos,blu_pos,turn)
            if turn < answer[0]:
                answer[0] = turn
            return
        moves = [[0,1],[0,-1],[1,0],[-1,0]]
        for m in moves:
            if (red_dep<=blu_dep or blu_clear) and not red_clear:
                tmp=ava_move(maze,red_pos,m,True) # 이동콛
                if tmp:
                    # red가움직임...
                    bef,ny,nx = tmp
                    if not (ny <mark> blu_pos[0] and nx </mark> blu_pos[1]):
                        maze[ny][nx] = [1,bef[1]] # 이동처리
                        goBox([ny,nx],blu_pos,red_dep+1,blu_dep,red_fin,blu_fin)
                        maze[ny][nx]= bef # 움직임 복귀
            if (red_dep>blu_dep or red_clear) and not blu_clear:
                tmp=ava_move(maze,blu_pos,m,False)
                if tmp:
                    # blu가움직임...
                    bef,ny,nx = tmp
                    if not (ny <mark> red_pos[0] and nx </mark> red_pos[1]):
                        maze[ny][nx] = [bef[0],1] # 이동처리
                        goBox(red_pos,[ny,nx],red_dep,blu_dep+1,red_fin,blu_fin)
                        maze[ny][nx]= bef # 움직임 복귀   
        return

    red_pos,blu_pos = False,False
    red_fin,blu_fin = False,False
    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if maze[i][j] != 5:
                if maze[i][j] == 1:
                    maze[i][j] = [1,0]
                    red_pos = [i,j]
                elif maze[i][j] == 2:
                    maze[i][j] = [0,1]
                    blu_pos = [i,j]
                else:
                    if maze[i][j] == 3:
                        red_fin = [i,j]
                    elif maze[i][j] == 4:
                        blu_fin = [i,j]
                    maze[i][j] = [0,0]

    # print(red_pos,blu_pos)
    goBox(red_pos,blu_pos,0,0,red_fin,blu_fin);

    return 0 if math.inf==answer[0] else answer[0]

def ava_move(maze,pos,move,isRed):
    y,x=pos
    dy,dx=move
    ny = y + dy
    nx = x + dx
    if ny<0 or nx <0 or ny>len(maze)-1 or nx>len(maze[0])-1:
        # 범위안에도 없음
        return False
    val = maze[ny][nx]
    if val <mark> 5 or (isRed and val[0] </mark> 1) or (not isRed and val[1] == 1):
        return False
    # 움직일 순잇음용
    if isRed:
        return [val,ny,nx]
    else:
        return [val,ny,nx]

    # 가능하움직임 벽 ㄴㄴ 격자 ㄴㄴ 방문한곳 ㄴㄴ

둘다먼저 움직일 수있음 but
계산횟수가 많아짐 예를들어
2>3턴넘어갈때

"""
n*m크기
시작>도착
각턴마다 상하좌우중인접한 한칸으로 움직여야함
방문햇던곳갈수없음
도착시 고정
수레끼리 자라바꿀수없음(부딪히면안됨)
dfs같은데용?
"""
import math
import traceback

def solution(maze):
    answer = [math.inf,len(maze)*len(maze[0])]# 빈칸 0 / 방문 빨,파 1,2/ 
    def goBox(red_pos,blu_pos,red_dep,blu_dep,red_fin,blu_fin):
        print(red_pos,blu_pos,red_dep,blu_dep,red_fin,blu_fin)
        turn = max(red_dep,blu_dep)
        red_clear = red_pos[0] <mark> red_fin[0] and red_pos[1] </mark> red_fin[1]
        blu_clear = blu_pos[0] <mark> blu_fin[0] and blu_pos[1] </mark> blu_fin[1]
        if turn>answer[1] or turn>=answer[0]:
            return
        if red_clear and blu_clear:
            print("도착!",red_pos,blu_pos,turn)
            if turn < answer[0]:
                answer[0] = turn
            return
        moves = [[0,1],[0,-1],[1,0],[-1,0]]
        for m in moves:
            if ((blu_dep-red_dep>=0 and blu_dep-red_dep<2) or blu_clear) and not red_clear:
                tmp=ava_move(maze,red_pos,m,True) # 이동콛
                if tmp:
                    # red가움직임...
                    bef,ny,nx = tmp
                    if not (ny <mark> blu_pos[0] and nx </mark> blu_pos[1]):
                        maze[ny][nx] = [1,bef[1]] # 이동처리
                        goBox([ny,nx],blu_pos,red_dep+1,blu_dep,red_fin,blu_fin)
                        maze[ny][nx]= bef # 움직임 복귀
            if ((red_dep-blu_dep>=0 and red_dep-blu_dep<2) or red_clear) and not blu_clear:
                tmp=ava_move(maze,blu_pos,m,False)
                if tmp:
                    # blu가움직임...
                    bef,ny,nx = tmp
                    if not (ny <mark> red_pos[0] and nx </mark> red_pos[1]):
                        maze[ny][nx] = [bef[0],1] # 이동처리
                        goBox(red_pos,[ny,nx],red_dep,blu_dep+1,red_fin,blu_fin)
                        maze[ny][nx]= bef # 움직임 복귀   
        return

    red_pos,blu_pos = False,False
    red_fin,blu_fin = False,False
    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if maze[i][j] != 5:
                if maze[i][j] == 1:
                    maze[i][j] = [1,0]
                    red_pos = [i,j]
                elif maze[i][j] == 2:
                    maze[i][j] = [0,1]
                    blu_pos = [i,j]
                else:
                    if maze[i][j] == 3:
                        red_fin = [i,j]
                    elif maze[i][j] == 4:
                        blu_fin = [i,j]
                    maze[i][j] = [0,0]

    # print(red_pos,blu_pos)
    goBox(red_pos,blu_pos,0,0,red_fin,blu_fin);

    return 0 if math.inf==answer[0] else answer[0]

def ava_move(maze,pos,move,isRed):
    y,x=pos
    dy,dx=move
    ny = y + dy
    nx = x + dx
    if ny<0 or nx <0 or ny>len(maze)-1 or nx>len(maze[0])-1:
        # 범위안에도 없음
        return False
    val = maze[ny][nx]
    if val <mark> 5 or (isRed and val[0] </mark> 1) or (not isRed and val[1] == 1):
        return False
    # 움직일 순잇음용
    if isRed:
        return [val,ny,nx]
    else:
        return [val,ny,nx]
    
    # 가능하움직임 벽 ㄴㄴ 격자 ㄴㄴ 방문한곳 ㄴㄴ