[프로그래머스]게임 맻 최단 거리

[42] 게임 맵 최단 거리

책 구매하기

문제 정보

• 분류: 그래프
• 정답률: 57%
• 권장 시간 복잡도: O(R * C)
• 핵심 키워드: BFS, 격자, 최단 거리, 거리 배열
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844

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

가중치가 없는 격자 최단 거리 문제라 BFS가 정석이다. 시작점에서 한 번만 BFS를 돌리고, 마지막 칸까지의 거리만 꺼내면 된다.

최단 거리나 연결성처럼 칸과 칸, 정점과 정점 사이를 따라가야 하는 문제는 결국 탐색 구조가 핵심이다. 방문 상태를 어떻게 정의하느냐가 정답을 거의 결정한다.

풀이 흐름

1. 시작점 (0,0)에서 BFS를 시작한다.
2. 이동 가능한 칸만 큐에 넣고 거리 배열을 갱신한다.
3. 도착점 거리가 남아 있으면 반환하고, 끝까지 -1이면 도달 불가다.

구현할 때 놓치기 쉬운 부분

이 문제는 가중치가 없는 격자 최단 거리 문제이므로 BFS가 맞다. 방문 체크를 너무 늦게 하거나, 한 번 방문한 칸을 다시 넣는 구조를 만들면 거리 계산이 쉽게 틀어진다.

파이썬 정답 코드

from collections import deque

def solution(maps):
  # 시작점 (0,0)에서 BFS를 시작한다.
  rows, cols = len(maps), len(maps[0])
  dist = [[-1] * cols for _ in range(rows)]
  q = deque([(0, 0)])
  dist[0][0] = 1

  # 이동 가능한 칸만 큐에 넣고 거리 배열을 갱신한다.
  while q:
    # 도착점 거리가 남아 있으면 반환하고, 끝까지 -1이면 도달 불가다.
    r, c = q.popleft()
    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 maps[nr][nc] == 1 and dist[nr][nc] == -1:
        dist[nr][nc] = dist[r][c] + 1
        q.append((nr, nc))

  return dist[rows - 1][cols - 1]

시간 복잡도

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

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

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