문제 출처

풀이과정

전체 코드

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