[PS] BOJ 12851 / 숨바꼭질 2

[PS] BOJ 12851 / 숨바꼭질 2
문제 링크: https://www.acmicpc.net/problem/12851
Thumbnail: Photo by loong xu (Unsplash)

어느덧 이런 유형의 문제는 BFS로 푸는게 보이기 시작했습니다.

풀이

BFS

BFS로 전체 구간을 탐색하면서, 다음 탐색할 노드로 [\(X - 1\), \(X + 1\), \(2 \times X\)]를 넣어주면 됩니다. 단, 다음에 탐색할 지점이 전체 구간 (\(0 \le x \le 100,000\)) 안에 있어야 합니다.

전체 코드

from collections import deque
input = open(0).readline
N, K = map(int, input().split())
if N == K:
    print("0\n1")
else:
    queue = deque((N, ))
    visited = [-1 for _ in range(100001)]
    visited[N] = 0
    count = 0
    while queue:
        x = queue.popleft()
        # 이미 K에 도달한 경우보다 더 오랜 시간 탐색하는 경우는 무시한다.
        if visited[K] != -1 and visited[K] < visited[x] + 1:
            continue
        # 다음 경우를 큐에 넣는다.
        for nx in (x - 1, x + 1, x * 2):
            # 방문하지 않았거나, 현재 위치에서 K에 도달하는 시간이 더 짧거나 같은 경우
            if 0 <= nx <= 100000 and (visited[nx] == -1 or visited[nx] >= visited[x] + 1):
                visited[nx] = visited[x] + 1
                if nx == K:
                    count += 1
                queue.append(nx)

    print(visited[K])
    print(count)

solution.py

고민했던 내용들

  • 처음에는 현재 위치 \(X\)가 \(K\)보다 작다면 \(X-1\)은 탐색하지 않아도 되지 않을까? 생각했는데, 의외로 \(X-1\)로 이동하는게 더 적은 시간이 걸리는 경우가 존재하는걸 깨달아 놀랐다. 당장 문제에 예시로 주어진 케이스가 그렇다.
    • N = 5, K = 17
      • 5 -> 4 -> 8 -> 16 -> 17 (4)
      • 5 -> 10 -> 9 -> 18 -> 17 (4)
  • 다음 경우를 큐에 넣기 전에, 이미 \(K\)에 도달한 경우의 수가 존재한다면 그보다 더 긴 시간 탐색하는 경우는 무시하게끔 조건문을 작성했다.
    • 없이도 문제 해결은 가능했으나, 최소 시간에 \(K\)에 도달한 경우가 존재함에도 그 이후의 경우들을 계속 탐색하는게 마음에 들지 않았다.