[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)
- N = 5, K = 17
- 다음 경우를 큐에 넣기 전에, 이미 \(K\)에 도달한 경우의 수가 존재한다면 그보다 더 긴 시간 탐색하는 경우는 무시하게끔 조건문을 작성했다.
- 없이도 문제 해결은 가능했으나, 최소 시간에 \(K\)에 도달한 경우가 존재함에도 그 이후의 경우들을 계속 탐색하는게 마음에 들지 않았다.