[프로그래머스] Lv.2 미로 탈출 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/159993
• 🔑 두 번의 BFS
  • 시작 위치에서 레버까지 BFS
  • 레버 위치에서 탈출 위치까지 BFS
  • 하나의 BFS 함수에 레버 여부를 매개변수로 두고 레버를 찾는지, 탈출구를 찾는지 구분
  • 레버를 못 찾거나, 탈출구를 못 찾으면 -1을 리턴

 

from collections import deque

def solution(maps):
    answer = 0
    
    def bfs(start, lever):
        visit = [[0] * len(maps[0]) for _ in range(len(maps))]
        dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
        q = deque([start])
        visit[start[0]][start[1]] = 1

        while q:
            x, y = q.popleft()

            for i in range(4):
                mx, my = x + dx[i], y + dy[i]
                
                if 0 <= mx < len(maps) and 0 <= my < len(maps[0]) and visit[mx][my] == 0 and maps[mx][my] != "X":
                    if not lever and maps[mx][my] == "L":   # 레버 찾기
                        return visit[x][y]
                    elif lever and maps[mx][my] == "E":     # 레버 찾은 후 출구 찾기
                        return visit[x][y]
                    else:                                   # 그냥 통로
                        q.append([mx, my])
                        visit[mx][my] = visit[x][y] + 1
        return -1
    
    # 시작 위치 찾기
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == "S":
                start = [i, j]
            elif maps[i][j] == "L":
                lever = [i, j]
                
    time_to_lever = bfs(start, False)   # 레버 찾기
    
    if time_to_lever == -1:
        return -1
    else:
        time_to_exit = bfs(lever, True) # 출구 찾기
        if time_to_exit == -1:
            return -1
        
    return time_to_lever + time_to_exit