[프로그래머스] 159993. 미로탈출 | BFS | 파이썬, 소스코드, 정답

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

프로그래머스

---

문제 요약

• 통로, 벽, 레버, 탈출구로 이루어진 미로가 주어진다.
• 레버로 이동한 후 탈출구로 이동하는 최단거리를 구하라

---

문제 조건

• S: 시작지점, E: 탈출구, L: 레버, O: 통로, X: 벽
• 상하좌우로 이동. 벽으로 된 칸은 이동 불가. 통로, 레버, 탈출구는 이동 가능. 같은 곳을 여러번 이동할 수 있음
• 탈출이 불가능한 경우 -1 반환

---

시행착오

• 내가 좋아하는 BFS문제. 딱히 어렵지는 않았지만 다른분들 코드 보니 BFS 부분을 메서드로 추출하셨는데 나는 그냥 무식하게 while문 두번 돌렸다 하핫~

---

접근방식

• 시작지점부터 레버까지의 최단거리를 구하고 레버부터 탈출구까지의 최단거리를 구하면 됨
• 노드끼리의 거리가 같으므로 BFS를 사용해서 최단거리를 구할 수 있음

---

소스코드

from collections import deque

def solution(maps):
    answer = 0
    N, M = len(maps), len(maps[0])
    matrix = [[0]*M for _ in range(N)]
    start_x, start_y = 0, 0

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

    for i in range(N):
        for j in range(M):
            if maps[i][j] == 'S':
                start_x, start_y = i, j
            elif maps[i][j] == 'X':
                matrix[i][j] = -1

    q = deque([(start_x, start_y)])
    while q:
        x, y = q.popleft()
        if maps[x][y] == 'L':
            answer = matrix[x][y]
            start_x, start_y = x, y
            break

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]

            if not(0 <= nx < N and 0 <= ny < M):
                continue

            if matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] + 1
                q.append((nx, ny))
    else:
        return -1

    matrix = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if maps[i][j] == 'X':
                matrix[i][j] = -1

    q = deque([(start_x, start_y)])
    while q:
        x, y = q.popleft()
        if maps[x][y] == 'E':
            answer += matrix[x][y]
            break

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]

            if not(0 <= nx < N and 0 <= ny < M):
                continue

            if matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] + 1
                q.append((nx, ny))
    else:
        return -1

    return answer