[프로그래머스]미로 탈출

[30] 미로 탈출

책 구매하기

문제 정보

• 분류: 트리
• 정답률: 42%
• 권장 시간 복잡도: O(R * C)
• 핵심 키워드: BFS, 레버, 최단 경로, 두 번 탐색
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/159993

문제를 읽을 때 체크할 포인트

출구만 바로 가면 되는 문제가 아니라 레버를 반드시 거쳐야 한다. 그래서 시작점에서 레버까지 한 번, 레버에서 출구까지 한 번, 최단 거리를 두 번 구하는 식으로 쪼개는 게 핵심이다.

한 번의 BFS로 끝나는 구조가 아니다. 레버를 당기기 전과 후의 이동 가능 상태가 다르다고 보고, 시작점에서 레버까지와 레버에서 출구까지를 따로 계산해야 식이 깔끔해진다.

풀이 흐름

1. 맵에서 시작점 S, 레버 L, 출구 E 좌표를 찾는다.
2. S에서 L까지 BFS로 최단 거리를 구한다.
3. L에서 E까지 다시 BFS를 하고 두 거리를 더한다.

구현할 때 놓치기 쉬운 부분

레버를 당기기 전과 당긴 뒤를 같은 상태로 보면 안 된다. 출구가 같더라도 레버를 누르기 전에는 갈 수 없는 길이 있을 수 있으므로 상태를 분리해 최단 거리를 계산해야 한다.

파이썬 정답 코드

from collections import deque

def solution(maps):
  # 맵에서 시작점 S, 레버 L, 출구 E 좌표를 찾는다.
  rows, cols = len(maps), len(maps[0])

  start = lever = end = None
  # S에서 L까지 BFS로 최단 거리를 구한다.
  for r in range(rows):
    for c in range(cols):
      if maps[r][c] == "S":
        start = (r, c)
      elif maps[r][c] == "L":
        lever = (r, c)
      elif maps[r][c] == "E":
        end = (r, c)

  def bfs(src, target):
    q = deque([(src[0], src[1], 0)])
    visited = [[False] * cols for _ in range(rows)]
    visited[src[0]][src[1]] = True

    while q:
      r, c, dist = q.popleft()
      if (r, c) == target:
        return dist

      for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and maps[nr][nc] != "X":
          visited[nr][nc] = True
          q.append((nr, nc, dist + 1))

    return -1

  first = bfs(start, lever)
  # L에서 E까지 다시 BFS를 하고 두 거리를 더한다.
  if first == -1:
    return -1
  second = bfs(lever, end)
  if second == -1:
    return -1
  return first + second

시간 복잡도

R은 행 수, C는 열 수이다.

격자 전체 칸 수가 R×C개이고, BFS나 DP가 각 칸을 많아야 한두 번씩만 처리한다. 그래서 행 수와 열 수의 곱이 그대로 전체 비용이 된다.

따라서 시간 복잡도는 O(R * C)이다.