수레 움직이기

BLUE_END = [0, 0] # 파란색 수레 목표 좌표 RED_END = [0, 0] # 빨간색 수레 목표 좌표 COL_LEN = 0 # 열 길이 ROW_LEN = 0 # 행 길이 # 방문 리스트, 수레 시작점 초기화 def initialize(maze, blue_start, red_start, blue_visited, red_visited): global BLUE_END, RED_END for i in range(ROW_LEN): for j in range(COL_LEN): if maze[i][j] == 1: # 빨간 수레의 시작 칸 red_visited[i][j] = 1 red_start = [i, j] elif maze[i][j] == 2: # 파란 수레의 시작 칸 blue_visited[i][j] = 1 blue_start = [i, j] elif maze[i][j] == 3: # 빨간 수레의 도착 칸 RED_END = [i, j] elif maze[i][j] == 4: # 파란 수레의 도착 칸 BLUE_END = [i, j] elif maze[i][j] == 5: # 벽 -> 갈 수 없으므로 방문 처리(case 1) red_visited[i][j] = 1 blue_visited[i][j] = 1 return blue_start, red_start, blue_visited, red_visited # 현재 수레가 격자 판 내부에 존재하는 지 확인하는 함수 def isin_boundary(cur_row, cur_col): global COL_LEN, ROW_LEN row_cond = (cur_row >= 0 and cur_row < ROW_LEN) col_cond = (cur_col >= 0 and cur_col < COL_LEN) return row_cond & col_cond def dfs(cur_blue, cur_red, blue_visited, red_visited): global RED_END, BLUE_END, COL_LEN, ROW_LEN deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 좌표 변화량 min_turns = 1e+8 # 최소 턴 reachable = False # 목표 지점 도달 가능 여부 if cur_blue == BLUE_END and cur_red == RED_END: # 각자의 목표 위치에 도착한 경우 return (True, 0) if cur_blue == cur_red: # 동시에 두 수레를 같은 칸에 위치한 경우 (case 4) return (False, 0) elif cur_blue == BLUE_END and cur_red != RED_END: # 파란 수레만 도착한 경우 for delta in deltas: # 빨간 수레만 이동 (case 3) red_row, red_col = delta[0]+cur_red[0], delta[1]+cur_red[1] if isin_boundary(red_row, red_col): # case 1 if red_visited[red_row][red_col] == 0: # case1 + case 2 red_visited[red_row][red_col] = 1 reach, turns = dfs(cur_blue, [red_row, red_col], blue_visited, red_visited) red_visited[red_row][red_col] = 0 if reach: # 빨간 수레가 목표 지점까지 도착할 수 있는 경우 reachable = True min_turns = min(min_turns, turns) elif cur_blue != BLUE_END and cur_red == RED_END: # 빨간 수레만 도착한 경우 for delta in deltas: # 파란 수레만 이동 (case 3) blue_row, blue_col = delta[0]+cur_blue[0], delta[1]+cur_blue[1] if isin_boundary(blue_row, blue_col): # case 1 if blue_visited[blue_row][blue_col] == 0: # case1 + case 2 blue_visited[blue_row][blue_col] = 1 reach, turns = dfs([blue_row, blue_col], cur_red, blue_visited, red_visited) blue_visited[blue_row][blue_col] = 0 if reach: # 파란 수레가 목표 지점까지 도착할 수 있는 경우 reachable = True min_turns = min(min_turns, turns) elif cur_blue != BLUE_END and cur_red != RED_END: # 두 수레 모두 이동해야 하는 경우 for delta in deltas: red_row, red_col = delta[0]+cur_red[0], delta[1]+cur_red[1] for delta in deltas: blue_row, blue_col = delta[0]+cur_blue[0], delta[1]+cur_blue[1] # 수레끼리 자리를 바꾸며 움직이는 경우 -> 더 이상 진행 불가능 (case 5) if ([blue_row, blue_col] == cur_red) and ([red_row, red_col] == cur_blue): continue else: if isin_boundary(red_row, red_col) and isin_boundary(blue_row, blue_col): if red_visited[red_row][red_col] == 0 and blue_visited[blue_row][blue_col] == 0: red_visited[red_row][red_col] = 1 blue_visited[blue_row][blue_col] = 1 reach, turns = dfs( [blue_row, blue_col], [red_row, red_col], blue_visited, red_visited ) red_visited[red_row][red_col] = 0 blue_visited[blue_row][blue_col] = 0 if reach: # 파란 수레와 빨간 수레 모두 목표 지점까지 도착할 수 있는 경우 reachable = True min_turns = min(min_turns, turns) return (True, min_turns+1) if reachable else (False, 0) def solution(maze): global RED_END, BLUE_END, COL_LEN, ROW_LEN blue_start, red_start = [0, 0], [0, 0] # 파란색, 빨간색 수레 시작 좌표 COL_LEN, ROW_LEN = len(maze[0]), len(maze) # 열 길이, 행 길이 blue_visited = [[0 for _ in range(COL_LEN)] for _ in range(ROW_LEN)] # 방문 리스트 (파란 수레) red_visited = [[0 for _ in range(COL_LEN)] for _ in range(ROW_LEN)] # 방문 리스트 (빨간 수레) blue_start, red_start, blue_visited, red_visited = initialize( maze, blue_start, red_start, blue_visited, red_visited ) _, answer = dfs(blue_start, red_start, blue_visited, red_visited) return answer