💡 문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
💭 접근
이 문제는 동생의 위치를 최단 시간에 찾아내는 문제로, BFS를 사용하여 해결할 수 있다. 이때 수빈이는 x+1, x-1, x+x로 움직일 수 있으며, 이러한 이동 방법에 따라 모두 탐색하면 된다.
이때, nx (수빈이의 다음 위치)를 입력의 최대인 100,000까지만 확인하는 이유는 다음과 같다.
ex) n = 50000 + x, k = 100000
이때 50000 + x의 경우 x만큼 뒤로가고 x2를 하면 찾는 시간은x+1이 되지만,
x2를 먼저 하게되면 2(50000 + x) = 100000 + 2x이고, 다시 2x만큼 뒤로 가야하므로 찾는 시간은2x+1이 된다.
따라서 nx가 100000을 넘는 경우를 지나는 경우는 최적해가 될 수 없다.
📒 코드
from collections import deque
def bfs(start):
graph[start] = 0
q = deque()
q.append(start)
while q:
x = q.popleft()
if x == k:
print(graph[x])
break
for nx in (x + 1, x - 1, x + x):
if 0 <= nx < 100001 and graph[nx] == -1:
graph[nx] = graph[x] + 1
q.append(nx)
n, k = map(int, input().split())
graph = [-1 for _ in range(100001)]
bfs(n)💭 후기
간단한 BFS 문제로, 쉽게 해결할 수 있었다.
🔗 문제 출처
https://www.acmicpc.net/problem/1697
