[프로그래머스] 미로탈출 - Level 3 (Python)

📌 문제 정보

미로탈출 Level 3

플랫폼

프로그래머스

유형

BFS, 그래프 탐색

언어

Python 3

풀이 시간

약 80분

풀이 날짜

2026.05.25

문제 링크

바로가기 ↗

---

🧩 문제 요약

격자 형태의 미로(maps)에서 출발지(S)부터 출구(E)까지 가는 최단 시간을 구하되, 반드시 레버(L)를 거쳐야 하는 문제

입력 조건:

• maps는 문자열 배열, 각 문자열은 미로의 한 행
• S: 시작 지점, E: 출구, L: 반드시 거쳐야 할 레버, O: 통로, X: 벽
• 상하좌우로만 이동 가능

출력 조건:

• 출발지에서 레버를 거쳐 출구까지 도달하는 최단 시간 반환
• 도달 불가능하면 -1 반환

---

💡 나의 접근 방식

1단계 - 처음 든 아이디어

단순 BFS로 S에서 E까지 최단거리를 구하면 될 줄 알았다. 그런데 문제 조건을 다시 보니 반드시 L을 거쳐야 한다는 제약이 있어서, 단순 최단거리 탐색만으로는 풀 수 없었다.

2단계 - 막혔던 부분

"레버를 거쳐야 한다"는 조건을 어떻게 BFS 상태에 녹여야 할지 헤맸다. 같은 좌표라도 레버를 밟기 전/후가 다른 의미를 가지는데, 일반적인 2차원 visited[y][x]로는 이 차이를 구분할 수 없었다.

3단계 - 해결 실마리

두 가지 방식으로 해결 가능하다는 걸 파악했다.

• 방식 A: visited를 [y][x][k] 3차원으로 만들어서, k=0(레버 안 밟음) / k=1(레버 밟음) 상태를 따로 관리. 다음 칸이 L이면 k를 1로 바꿔서 큐에 넣고, 도착 조건도 (y,x)==E and k==1로 검사.
• 방식 B: 어차피 S→L→E 순서가 고정되어 있으니, BFS를 두 번 돌려서 S→L 최단거리 + L→E 최단거리를 그냥 더하면 된다. 이러면 상태 관리 없이 평범한 BFS로 끝.

핵심 아이디어:

• 경로에 "거쳐야 하는 지점"이 있다면, 상태를 확장하거나(3차원 visited) 구간을 나눠서(BFS 분리) 풀 수 있다
• 둘 다 정답이지만 접근 방식이 완전히 다르다는 게 인상적이었음

---

✅ 최종 풀이 코드 (방식 A - BFS 1번, 상태 확장)

from collections import deque


def is_valid_move(ny, nx, n, m, maps):
    return 0 <= ny < n and 0 <= nx < m and maps[ny][nx] != "X"


def append_to_queue(ny, nx, k, time, visited, q):
    if not visited[ny][nx][k]:
        visited[ny][nx][k] = True
        q.append((ny, nx, k, time + 1))


def solution(maps):
    n, m = len(maps), len(maps[0])
    visited = [[[False for _ in range(2)] for _ in range(m)] for _ in range(n)]

    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    q = deque()
    end_y, end_x = -1, -1

    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                q.append((i, j, 0, 0))
                visited[i][j][0] = True
            if maps[i][j] == "E":
                end_y, end_x = i, j

    while q:
        y, x, k, time = q.popleft()

        if y == end_y and x == end_x and k == 1:
            return time

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

            if not is_valid_move(ny, nx, n, m, maps):
                continue

            if maps[ny][nx] == "L":
                append_to_queue(ny, nx, 1, time, visited, q)
            else:
                append_to_queue(ny, nx, k, time, visited, q)

    return -1

---

📊 복잡도 분석

구분 복잡도 근거

시간 복잡도	O(N²)	맵을 N×N 정사각형으로 가정 시, 전체 칸 N² × 4방향 탐색 = O(4N²) → 상수 생략 시 O(N²)
공간 복잡도	O(N²)	visited 배열이 [N][M][2] 크기로 칸 수에 비례

visited가 3차원이라 일반 BFS보다 메모리를 2배 쓰지만, 시간복잡도 자체는 O(N²)로 동일하다. 레버 상태(k)가 0/1 두 가지뿐이라 상수 배수만 늘어난 것.

---

❌ 오답 노트

시도 틀린 이유 수정 내용

1차	visited[y][x] 2차원으로만 관리 → 레버를 밟기 전/후 상태를 구분 못해서 레버 없이 도착한 경로가 먼저 방문 처리되어 정답을 못 찾음	visited[y][x][k] 3차원으로 변경, 레버 상태별로 따로 방문 체크
2차	도착 조건을 (y,x)==E로만 검사 → 레버 안 밟고 도착해도 정답 처리됨	조건에 k==1 추가하여 반드시 레버를 밟은 상태에서만 정답 인정
3차	통과 ✅	-

---

🔄 다른 풀이 방법

BFS 2번 (S→L, L→E 구간 분리)

from collections import deque


def solution(maps):
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    for i in range(len(maps)):
        for j in range(len(maps[i])):
            if maps[i][j] == "S":
                s = (i, j)
            elif maps[i][j] == "L":
                l = (i, j)
            elif maps[i][j] == "E":
                e = (i, j)

    def bfs(s, e):
        queue = deque()
        visited = [[False] * len(maps[0]) for _ in range(len(maps))]

        queue.append((s[0], s[1], 0))
        visited[s[0]][s[1]] = True

        while queue:
            y, x, dist = queue.popleft()

            if (y, x) == e:
                return dist

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

                if 0 <= ny < len(maps) and 0 <= nx < len(maps[0]):
                    if maps[ny][nx] != "X" and not visited[ny][nx]:
                        visited[ny][nx] = True
                        queue.append((ny, nx, dist + 1))

        return -1

    s_to_l = bfs(s, l)
    l_to_e = bfs(l, e)

    if s_to_l == -1 or l_to_e == -1:
        return -1

    return s_to_l + l_to_e

방식 A vs 방식 B 비교:

• 방식 A (상태 확장): BFS를 1번만 돌리지만, visited를 3차원으로 관리해야 해서 구현이 복잡함
• 방식 B (BFS 분리): "S→L→E는 순서가 고정"이라는 점을 이용해 평범한 BFS를 2번 호출. 코드가 단순하고 실수할 포인트가 적음
• 시간복잡도는 둘 다 O(N²)로 동일하지만, 방식 B가 직관적이고 디버깅하기 쉬워서 실전에서는 더 선호

---

📝 배운 점 & 회고

• ✏️ 새로 알게 된 것: 경로에 "반드시 거쳐야 하는 지점"이 있을 때는 ① visited에 상태 차원을 추가하거나 ② 구간별로 BFS를 분리하는 두 가지 전략이 있다.
• ✏️ 새로 알게 된 것: visited[y][x][k]처럼 상태를 추가하면, 같은 좌표라도 상태가 다르면 별개의 노드로 취급해서 BFS가 정상 동작한다.
• ⚠️ 실수했던 점: 처음엔 2차원 visited로 시작했다가 레버 조건을 놓쳤다. 문제에 "특정 지점을 반드시 거쳐야 한다"는 조건이 있으면 바로 상태 확장이나 BFS 분리를 떠올려야 한다.
• 💬 한 줄 요약: 같은 좌표도 상태가 다르면 다른 노드다. 거쳐야 할 지점이 있다면 상태를 쪼개거나 구간을 나누자!