백준 1697번 - 숨바꼭질

숨바꼭질 문제 바로 가기

풀이 코드

import sys
from collections import deque
input = sys.stdin.readline

MAX = 10**5

def bfs(n,k):
    dist = [-1] * (MAX+1)
    q = deque([n])
    dist[n] = 0

    while q:
        x = q.popleft()

        if x == k:
            return dist[x]

        for nx in (x-1, x+1, x*2):
            if 0<=nx<=MAX and dist[nx] == -1:
                dist[nx] = dist[x]+1
                q.append(nx)
n,k = map(int, input().split())
print(bfs(n,k))
  

해결 전략:

1) 한 번 이동할 때마다 시간은 1초 증가하며 이동 비용이 모두 동일하다. 따라서 BFS 사용하였다.

dist 배열의 의미

• dist[x] == -1: 아직 한 번도 방문하지 않은 위치
• dist[x] >= 0: 해당 위치까지 도달하는 데 걸린 시간

• 즉, dist 배열은 방문 여부와 시간 기록을 동시에 관리한다.

  시작점 초기화

• dist[n] = 0

  출발 위치는 이미 도착해 있는 상태이므로, 시간은 0초이며 방문 완료 상태로 표시해야 한다.

어려웠던 부분

1. dist 배열이 방문 체크와 시간 기록을 동시에 한다는 점
2. 왜 dist[nx] == -1 조건이 반드시 필요한지
3. BFS에서 처음 도착이 왜 최단 거리인지에 대한 직관
4. 큐가 “탐색 순서를 보장하는 장치”라는 점