문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 1
5 17
예제 출력 1
2
나의 풀이
- 처음에는 수빈이가 현재 위치에서 방문 가능한 하위 노드가 3개인 그래프를 연상하고 BFS로 풀이했다. 그러나 하위 노드의 방문 여부를 체크하는 과정을 구현하지 않아 지나치게 많은 노드를 큐에 삽입해 메모리 초과가 발생했다. 처음 이 문제를 풀 때는 이미 방문한 위치여도 새로운 경로에 포함되면 방문해야 한다고 생각했다. 그러나 생각해보면 최단 거리를 구해야 하므로 깊이가 얕은 노드에서 이미 해당 위치를 방문했다면 굳이 또 방문할 필요가 없다는 것을 알 수 있다. 따라서 visited 배열을 만들어 BFS에서 메모리 초과가 발생하지 않도록 주의해야 한다.
- 이 문제의 방문 가능한 상태는 아래와 같이 트리로 시각화할 수 있다. 이 문제에서 가장 주의해야 하는 점은 경로의 비용이 동일하지 않다는 점이다. 순간이동을 하는 경우에는 0초가 소요되므로 순간이동 노드의 방문 우선 순위를 높게 두어야 한다. 수빈이와 동생이 각각 2와 5에 위치한 경우를 트리로 나타낸 아래 그림을 기준으로 보면 이해가 빠를 것이다. 파이썬의 deque 자료구조를 사용해 순간이동 노드는 큐의 왼쪽에 삽입하고 걸어가는 노드는 큐의 오른쪽에 삽입하도록 구현했다.
- 큐에 우선순위가 높은 노드를 먼저 삽입하는 아이디어가 한 번에 떠오르지 않아 꽤 어렵다고 느껴졌다. 간선의 비용이 다른 그래프를 탐색하는 문제를 풀게 된다면 응용해 봐야겠다..
import sys
from collections import deque
input = sys.stdin.readline
def BFS(N, K):
max_pos = 100001
visited = [False] * max_pos
queue = deque()
queue.append((N, 0))
visited[N] = True
while queue:
curr_pos, curr_time = queue.popleft()
if curr_pos == K:
return curr_time
next_pos = curr_pos * 2
if 0 <= next_pos < max_pos and not visited[next_pos]:
visited[next_pos] = True
queue.appendleft((next_pos, curr_time))
for next_pos in [curr_pos - 1, curr_pos + 1]:
if 0 <= next_pos < max_pos and not visited[next_pos]:
visited[next_pos] = True
queue.append((next_pos, curr_time + 1))
N, K = map(int, input().split())
print(BFS(N, K))
SAY CHEESE