📄 문제
백준
난이도 : Silver 1
문제 제목 : 숨바꼭질
✏️ 풀이 1
import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())
dist = [-1] * 100001
deq = deque([n])
dist[n] = 0
while deq:
current_point = deq.popleft()
current_time = dist[current_point]
if current_point == k:
print(current_time)
sys.exit(0)
for v in [current_point - 1, current_point + 1, current_point * 2]:
if v < 0 or v > 100000:
continue
if dist[v] != -1:
continue
deq.append(v)
dist[v] = current_time + 1✅ Check Point 1: 우선 이 문제가 BFS 문제임을 파악해야 한다.
수빈이가 X에 있을 때 X - 1 , X + 1 , 2X 로 이동하는 것을 BFS로 처리할 수 있기 때문에, 이 문제는 BFS로 푸는 것이 좋다.
✅ Check Point 2: 이 문제는 BFS 중에서도 BFS의 기본적인 응용 문제인 '1차원에서의 BFS' 문제이다.
1차원을 BFS로 어떻게 접근해야 하는지 감이 잘 안온다면 다음을 읽어보자.
예를 들어, 5에서 시작할 때 5에서 갈 수 있는 위치는 4, 6, 10이고 소요 시간은 1이다. 그리고 4의 위치에서 갈 수 있는 위치는 3, 5, 8인데 5는 이미 처음에 지나쳤던 시작 위치이기 때문에 3, 8만 소요 시간이 2로 저장된다.
✅ Check Point 3: 수빈이가 이동할 수 있는 범위를 잘 찾아야 한다.
초기에 0에서 100,000 사이에 있는 것이지 그 이상으로 벗어날 수도 있다. 그러나 음수로 가거나 100,000을 벗어난다면 가장 빠른 경우가 될 수는 없을 것이다. (100,000 초과 시에는 무조건 -1만 계속 할 것이기 때문) 따라서 가장 빠르게 찾는 상황에서는 아무리 멀리가도 200,000을 넘지 않는다.
더해서 100,000을 나가는 것 자체가 손해이다. *2 후 -1 을 계속할 바에야 -1 후 *2 를 하는 게 낫기 때문이다.
따라서 범위는 0에서 100,000 사이일 것이다.
BFS를 알고 있으면서 위의 체크 포인트를 유의하고 위의 코드를 본다면 이해가 쉽게 될 것이다.
📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '1697. 숨바꼭질'
GitHub - [9강] BFS/연습문제 '1697. 숨바꼭질'
BFS의 대표적인 응용 유형인 '1차원에서의 BFS' 유형의 가장 기본적인 문제라 정리를 해보았다.
