[Programmers] 미로 탈출 (BFS Lv. 2) - Python

1. 문제

미로 탈출

2. 풀이

from collections import deque

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    flag = False
    
    def bfs(sx, sy, sec):
        nonlocal flag
        q = deque()
        v = [[0] * m for _ in range(n)]
        
        q.append((sx, sy))
        v[sx][sy] = sec
        
        while q:
            cx, cy = q.popleft()
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = cx + dx, cy + dy              
                if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 'X' and v[nx][ny] == 0:
                    if maps[nx][ny] == 'L':
                        flag = True
                        return v[cx][cy]
                    if maps[nx][ny] == 'E' and flag:                       
                        return v[cx][cy] + 1
                    q.append((nx, ny))
                    v[nx][ny] = v[cx][cy] + 1
        return -1
        
                    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 'S':
                result = bfs(i, j, 1)
                break
    if not flag:
        return -1
    else:
        for i in range(n):
            for j in range(m):
                if maps[i][j] == 'L':
                    answer = bfs(i, j, result)
    return answer

3. 로직

1. bfs 함수는 너비 우선 탐색 (BFS) 을 사용하여 시작 지점에서 레버까지, 레버에서 도착 지점까지 이동하는 최단 거리를 계산한다.

2. BFS를 통해 각 통로를 탐색하면서, 레버를 찾으면 flag 값을 True 로 설정하고 현재까지의 걸린 시간을 반환한다.

3. 만약 레버에 도달할 수 없는 경우 ( flag 값이 False 인 경우 ) -1을 반환한다.

4. 또 한 번의 BFS를 통해 각 통로를 탐색하면서, 출구를 찾으면 현재까지 걸린 시간을 반환한다.

5. 만약 출구에 도달할 수 없는 경우 -1을 반환한다.

최종적으로 함수는 'S' 위치에서 BFS를 시작하고, 레버 'L'을 찾아 해당 위치에서 BFS를 다시 시작하여 'E' 위치 까지 최단 시간을 계산한다.