[programmers] Lv.2 미로 탈출 (python)

✏️ 문제

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.
미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

 

🤖 알고리즘

 

#BFS 

 

 

🤯 풀이 방법

 

레버를 찾든 출구를 찾든 같은 BFS 로직을 사용하기 때문에 함수 하나에 레버를 찾는지, 출구를 찾는지 여부와 소요 시간을 파라미터로 사용했다.

시작점을 찾고, 레버를 찾으면 그 레버의 좌표와 찾기까지의 소요시간을 리턴하게 하고

거기서 찾은 좌표로 다시 함수를 돌려 출구를 찾으면 소요시간만을 리턴하게 했다.

 

 

👾 구현 코드 (파이썬)

from collections import deque

def solution(maps):
    def find(i, j, w, cnt): # w: 레버를 찾는지 출구를 찾는지 여부, cnt: 현재까지 소요시간
        visited = [[0] * c for _ in range(r)]
        visited[i][j] = 1

        q = deque()
        q.append([i, j, cnt])
        while q:
            ii, jj, cntt = q.popleft()
            for k in range(4):
                ni, nj = ii + di[k], jj + dj[k]

                if 0 <= ni < r and 0 <= nj < c and maps[ni][nj] == w:
                    if w == "L":
                        # 레버를 찾으면 좌표와 현재까지 소요 시간 리턴
                        return [ni, nj, cntt + 1]
                    else:
                        # 출구를 찾으면 소요 시간만 출력
                        return cntt

                if 0 <= ni < r and 0 <= nj < c and visited[ni][nj] == 0 and maps[ni][nj] != "X":
                    visited[ni][nj] = 1
                    q.append([ni, nj, cntt + 1])
        
        # 출구 찾지 못한 경우 -1
        if w == "E":
            return -1
        
    
    c = len(maps[0])
    r = len(maps)
    answer = 0
    
    # 오른쪽, 아래, 왼쪽, 위
    di = [0, 1, 0, -1]
    dj = [1, 0, -1, 0]
    
    for i in range(r):
        for j in range(c):
            if maps[i][j] == 'S':
                lever = find(i, j, "L", 1)
                # 레버 찾지 못한 경우 -1
                if lever == None:
                    return -1
                else:
                    return find(lever[0], lever[1], "E", lever[2])