[Python] 프로그래머스(Programmers): 미로탈출

💁🏻  문제

프로그래머스

---

🤷🏼‍♀️  문제 설명

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

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

• 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
• 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

 

⚙️  풀이

➀ 경로를 저장할 필요가 없고 ➁이미 방문한 지점도 다시 방문할 수 있으므로 BFS로 접근하면 된다.
우선순위가 높은 경우(=탈출하는데 가장 적은 시간이 소요되는 경로)부터 순차적으로 탐색을 수행해서 최적의 해를 구해내면 되므로
자료구조로는 heapq를 사용하였다.

이 문제의 경우, 미로를 빠져나가기 전에 반드시 레버를 당겨야 한다는 조건이 있으므로,
(시작점~레버), (레버~출구) 이렇게 두 번으로 나누어 탐색을 수행한다. 만약 둘 중 하나라도 탈출할 수 없는 경로가 있다면 -1을 return한다.

탐색문제를 너무 오래간만에 풀었는지 이걸 DFS로 접근하려 했다. 기본을 잊은 바보가 되었다. 화이팅화이팅

import heapq

dx, dy = [1, 0, -1, 0], [0, -1, 0, 1]


def bfs(heap, end, _maps, _visited):
    while heap:
    	# 제일 빠르게 탈출할 수 있는 경로를 돌고 있는 지점부터 pop
        value, x, y = heapq.heappop(heap)
        if _maps[x][y] == end:
            return value
        if _maps[x][y] != 'X':
        	# 벽이 아닌 경우, 상하좌우로 이동할 수 있는 경우의 수를 탐색하고 heap에 추가한다
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if 0 <= nx < len(_maps) and 0 <= ny < len(_maps[0]) and not _visited[nx][ny]:
                    _visited[nx][ny] = 1
                    heapq.heappush(heap, (value + 1, nx, ny))
    return -1


def solution(maps):
    heap_s = []
    heap_l = []

    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 'S':
                heapq.heappush(heap_s, (0, i, j))
            elif maps[i][j] == 'L':
                heapq.heappush(heap_l, (0, i, j))

	# (시작점~레버)에 대한 경로 탐색
    visited = [[0 for _ in range(len(maps[0]))] for _ in range(len(maps))]
    visited[heap_s[0][1]][heap_s[0][2]] = 1
    s_to_l = bfs(heap_s, 'L', maps, visited)

	# 방문여부를 저장한 배열을 초기화하고 (레버~출구)에 대한 경로 탐색
    visited = [[0 for _ in range(len(maps[0]))] for _ in range(len(maps))]
    visited[heap_l[0][1]][heap_l[0][2]] = 1
    l_to_e = bfs(heap_l, 'E', maps, visited)
    
    # 둘 중 한 경로라도 탈출이 불가한 경우 -1을, 탈출이 가능한 경우 필요한 최소 시간을 return
    answer = -1 if s_to_l == -1 or l_to_e == -1 else (s_to_l + l_to_e)
    
    return answer