프로그래머스[ LV2 | Python ] 미로찾기

링크

https://school.programmers.co.kr/learn/courses/30/lessons/159993#

풀이

벽(X), 레버 (L), 출구(E), 시작점(S), 통로(O) 로 이뤄진 미로를 아래의 조건에 맞춰 탈출 할 수 있는 최소 비용을 반환하는 그래프 탐색 문제

1. 미로를 탈출하기 위해서는 시작점에서 레버를 당긴 후 출구로 향해야한다.

2. 벽은 통과할 수 없다.

3. 레버나 출구는 지나다닐 수 있다.

1. 방문 리스트, 방향 리스트를 정의한다.
   a. 이 때 방문 배열은 다른 루트에서 해당 인덱스로 접근하고 있는 탐색과 비교하기 위해 INF로 구성한다.
2. 레버, 출구, 시작점의 각 인덱스를 미리 저장한다.
3. 입구 → 레버로의 bfs를 수행한다.
   a. 다른 루트로도 접근할 수 있어야 하므로 탐색 시작 루트로 부터 1을 가산해가며 탐색한다.
   b. 다른 루트로부터의 탐색이 더 최소 값을 가진다면 해당 비용으로 수정한다.
4. 레버 → 출구로의 bfs를 수행한다.
   a. 지나왓던 길을 돌아다닐 수 있어야 하므로 방문배열을 다시 초기화한다.
5. 3과 4의 결과를 통해 얻어낸 비용을 더해서 결과를 반환한다. 도달할 수 없는 경우 (반환 값이 -1, 음수인 경우) -1을 반환한다.

코드

Python

from collections import deque

def solution(maps):
    INF = float('inf')
    v = [[INF] * len(maps[0]) for _ in range(len(maps))]
    dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    def bfs(start, end):
        q = deque()
        q.append(start)
        v[start[0]][start[1]] = 1
        while q:
            nx, ny = q.popleft()

            if [nx, ny] == end:
                return v[nx][ny]-1

            for dx, dy in dirs:
                x, y = nx + dx, ny + dy
                if 0 <= x < len(maps) and 0 <= y < len(maps[0]) and maps[x][y] != 'X' and v[x][y] == INF:
                    v[x][y] = min(v[x][y], v[nx][ny]+1)
                    q.append([x, y])
        return -1

    lever = [0, 0]
    exit = [0, 0]
    start = [0, 0]

    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 'L':
                lever = [i, j]
            elif maps[i][j] == 'E':
                exit = [i, j]
            elif maps[i][j] == 'S':
                start = [i, j]

    startToLever = bfs(start, lever)
    v = [[INF] * len(maps[0]) for _ in range(len(maps))]
    leverToExit = bfs(lever, exit)

    return startToLever + leverToExit if not -1 in [startToLever, leverToExit] else -1