[PS] 백준 1697번: 숨바꼭질

오늘은 백준의 1697번 숨바꼭질 문제를 풀어보겠습니다.

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제

# Input:
5 17

# Output:
4

풀이 1: 단순하게 풀기

주어진 예제에서 수빈이는 5에 있고, 동생은 17에 있다. 어떻게 하면 가장 빨리 만날 수 있을까? 가장 먼저 떠오르는 방법은 모든 경로를 탐색하는 것이다.

5 -> 4 -> 8 -> 16 -> 17 (4초)
5 -> 10 -> 9 -> 18 -> 17 (4초)
5 -> 6 -> 12 -> 24 -> ... 
...

이런 식으로 모든 경로를 살펴보면 최단 경로를 찾을 수 있다. 하지만 좌표 범위가 0부터 100,000까지기 때문에 모든 경우를 탐색하면 경우의 수가 기하급수적으로 늘어나서 시간 초과가 날 수밖에 없다.

 

풀이 2: 최적화

문제의 핵심을 다시 살펴보자. 

• A에서 B로 가기 위한 최단 시간을 구해야 한다.
• 모든 이동 비용은 1초로 동일하다.

이 두 조건을 보면 너비 우선 탐색(BFS)이 떠오른다. BFS는 말 그대로 "한 단계씩 넓혀가는 탐색"이다. 즉, 1초에 갈 수 있는 위치 -> 2초에 갈 수 있는 위치 -> ... 이런 식으로 시간이 지날수록 탐색 범위를 한 단계씩 확장한다. 그렇기 때문에 처음 어떤 위치에 도착했을 때의 시간이 곧 그 그 위치까지의 최단 시간이 된다. 

 

여기서 중요한 점은 이미 방문한 위치는 다시 방문할 필요가 없다는 것이다. 처음 도착했을 때가 가장 최단 시간이라는 점이 보장되기 때문이다. 예를 들어, 5에 2초 만에 도착했다면, 3초나 4초가 걸렸을 때, 다시 5를 방문해서 확인할 필요가 없다. 따라서 visited라는 배열을 하나 만들어서 "이미 탐색한 위치"를 표시해볼 수 있다. 그리고 큐에 넣을 때, 방문 여부를 체크해서 같은 위치를 중복해서 탐색하지 않도록 한다. 이렇게 하면 BFS 탐색을 훨씬 효율적으로 진행할 수 있다.

 

이 아이디어로 위의 예제를 다시 한번 풀어보자.

• 0초 (시작 위치): {5}
• 1초 (한번 이동): {4, 6, 10}
• 2초 (두 번 이동)
  4에서 갈 수 있는 위치: {3, 8}
  6에서 갈 수 있는 위치: {7, 12}
  10에서 갈 수 있는 위치: {9, 11, 20}
• 3초 (세 번 이동)
  3에서 갈 수 있는 위치: {2}
  8에서 갈 수 있는 위치: {16}
  7에서 갈 수 있는 위치: {14}
  12에서 갈 수 있는 위치: {13, 24}
  9에서 갈 수 있는 위치: {18}
  11에서 갈 수 있는 위치: {22}
  20에서 갈 수 있는 위치: {19, 21, 40}
• 4초 (네 번 이동)
  ...
  16에서 갈 수 있는 위치: {15, 17, 32}

구현 코드

from collections import deque

MIN, MAX = 0, int(1e5)
N, K = map(int, input().split())

if N >= K:
	print(N - K)
    exit()

q = deque()
visited = [False] * (MAX + 1)

q.append((N, 0))
visited[N] = True

while q:
	position, level = q.popleft()

	if position == K:
		print(level)
		exit()

	for next_position in [position + 1, position - 1, position * 2]:
		if ((0 <= next_position <= MAX) and not visited[next_position]):
			q.append((next_position, level + 1))
			visited[next_position] = True

알고리즘 분석

문제에서 탐색 가능한 위치의 범위는 0 ~ 100,000이다. (즉, MIN = 0, MAX = 100,000)

• 시간 복잡도: O(MAX) = O(100,000)
  BFS는 각 위치를 최대 한 번만 방문한다. 가능한 위치가 총 100,001개로 주어졌으므로, 최악의 경우 모든 위치를 한 번씩 확인해도 대략 10만 번 수준의 연산이면 충분하다.
• 공간 복잡도: O(MAX) = O(100,000)
  방문 여부를 저장하기 위해 사용하는 visited 배열 크기는 100,001에 비례한다. 또, 탐색 과정에서 사용하는 큐도 최악의 경우에는 확인해야 할 위치 수만큼 커질 수 있다. 따라서 전체 메모리 사용량 역시 O(MAX)로 표현할 수 있다.