159993 미로탈출(프로그래머스)

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

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

 

S에서 출발해서 레버로 도착하고

레버에서 E까지 가야되는 문제였습니다.

탈출 할 수 없으면 -1을 반환해야합니다.

DFS로 풀게되면 모든 루트를 구해서 최소값을 가져와야 합니다.

따라서 BFS를 통해 미로의 최솟값을 구하는 문제였습니다.

 

from collections import deque
def solution(maps):
    # s -> l -> e
    n = len(maps[0])  # 가로
    m = len(maps)  # 세로
    StoL = [[-1]*n for _ in range(m)]
    LtoE = [[-1]*n for _ in range(m)]
    E = None
    for row in range(m):
        for col in range(n):
            if maps[row][col] == "S":
                S = (row, col)
                StoL[row][col] = 0
                break

    SLq = deque([S])
    LEq = deque()

    def SLbfs():
        while(SLq):
            row, col = SLq.popleft()
            for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                nr = dr + row
                nc = dc + col
                if nr >= m or nr < 0 or nc >= n or nc < 0:
                    continue
                if maps[nr][nc] == "L":
                    LEq.append((nr, nc))
                    LtoE[nr][nc] = 0
                    return StoL[row][col] + 1
                if maps[nr][nc] != "X" and StoL[nr][nc] == -1:
                    SLq.append((nr, nc))
                    StoL[nr][nc] = StoL[row][col] + 1
        return -1

    def LEbfs():
        while(LEq):
            row, col = LEq.popleft()
            for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                nr = dr + row
                nc = dc + col
                if nr >= m or nr < 0 or nc >= n or nc < 0:
                    continue
                if maps[nr][nc] == "E":
                    return LtoE[row][col] + 1
                if maps[nr][nc] != "X" and LtoE[nr][nc] == -1:
                    LEq.append((nr, nc))
                    LtoE[nr][nc] = LtoE[row][col] + 1
        return -1

    sl = SLbfs()

    if sl == -1:
        return -1
    le = LEbfs()
    if le == -1:
        return -1

    return sl + le