[Python 문제 풀이] 프로그래머스 '미로 탈출'

ProgrammersLv.2 '미로 탈출' 파이썬 코드 및 풀이

대표적인 BFS문제, 근데 이제 경유노드를 곁들인

조건 파악

1. mpas는 최대 100x100이므로 N(max) = 10,000이다.
2. 경유노드(L:레버) 한 곳을 거쳐야 하므로 2N(max) = 20,000이며 시간복잡도 O(N)만에 풀면 된다.

접근

1. 최단경로를 구하기 위해 BFS로 푼다.
2. 경유노드가 있기 때문에 BFS를 두 번 한다.
 

의사 코드

시작점부터 L까지 BFS탐색
경로의 길이 저장
L부터 E까지 BFS탐색
최종 경로 반환

구현

from collections import deque

def solution(maps):
    rows,cols = len(maps), len(maps[0])
    r,c,distance = 0,0,0 # 시작 위치, 이동 거리 초기화
    dr = [-1, 1, 0, 0] # 이동 방향: 상, 하, 좌, 우
    dc = [0, 0, -1, 1]
    path = deque() # 경로를 저장할 큐 생성
    visited = [[False for _ in range(cols)] for _ in range(rows)] # 방문 여부 저장할 리스트 초기화
    opened = False # 특정 지점을 방문하여 큐와 방문 여부 리스트 초기화할지 여부 초기화
    
    # 시작 위치 (S) 찾기
    for i,row in enumerate(maps) :
        if 'S' in row :
            j = row.index('S')
            r,c,distance = i,j,0
            visited[i][j] = True # 시작 위치 방문 여부 체크
    
    # BFS 탐색 시작
    while True :
        for i in range(4) :
            x = [r + dr[i],c + dc[i]] # 다음 위치 계산
            if 0 <= x[0] < rows and 0 <= x[1] < cols and not visited[x[0]][x[1]] and maps[x[0]][x[1]] != 'X':
                path.append([x[0], x[1], distance + 1]) # 큐에 다음 위치 추가
                visited[x[0]][x[1]] = True # 다음 위치 방문 여부 체크

        if len(path) != 0 :
            r,c,distance = path.popleft() # 큐에서 다음 위치 가져오기
        else :
            distance = -1 # 경로가 없는 경우
            break
        
        if not opened and maps[r][c] == 'L' : # L 지점에 처음 도착한 경우
            opened = True # L 지점 방문 체크
            visited = [[False for _ in range(cols)] for _ in range(rows)] # 방문 여부 리스트 초기화
            visited[r][c] = True # L 지점 방문 체크
            path = deque() # 경로 큐 초기화
            path.append([r, c, distance]) # L 지점부터 다시 BFS 탐색 시작
        
        if opened and maps[r][c] == 'E' : # E 지점에 도착한 경우
            break
    
    return distance # E 지점까지의 최단 거리 반환