문제 이해
숨바꼭질 문제와 매우 유사한 문제이다.
차이점으로는 X2를 할때는 시간이 지나지 않는다는 것이다.
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
문제 접근
전에 숨바꼭질에서 시간체크 방법을 다른 방법을 사용해서 해보겠다고 했기 때문에 그렇게 진행했다.
visited에 false가 아니라 값을 넣어서 BFS를 진행할 때마다 1씩 더해주면서 시간을 체크해주었다.
문제 풀이
우선 BFS의 내부를 보면 아래와 같다.
초기 시간을 visited[cur] = 0을 통해 초기화해주고, 만약 초기에 입력한 cur 즉 N과 K가 같다면 0초가 걸리기 때문에 BFS를 들어가지 않고 바로 0을 return 해주도록 한다.
이제 while문으로 들어가는데 종료조건으로 n==K일 경우에 visited[K]를 return 하면서 함수를 종료한다. visited[K]에는 K까지 도달하기에 걸린 시간이 담겨져있다.
for문을 보면 n+1, n-1, 2n을 모두 시행해보고 조건에 부합하면 q에 더해준다. 이때 중요한것이 n+1, n-1, 2n의 순서이다. 순서는 2n이 가장 먼저 와야한다. 그 이유는 2를 곱하는 순간이동은 0초가 소요되기 때문에 우선순위가 가장 높은것이다.
그 다음으로 n+1, n-1이 있는데 n-1이 먼저와야한다.
그 이유는 반례로 입력 4 6이 입력되었을 때 본래의 정답이라면 4 -> 3 -> 6으로 1이 출력되어야 하지만 n+1이 먼저 올 경우에는 4 -> 5 -> 6으로 2가 출력되기 때문이다.
이러한 반례때문에 n-1이 먼저 와야한다. 따라서 for next_n in (2*n, n-1, n+1):의 순서가 되어야한다.
조건문에서는 next_n이 2*n인지 아닌지를 확인하여 1을 더해줄지 말지를 생각하면 된다.
def bfs(cur):
q = deque([])
q.append(cur) # q에 초기값을 넣어준다.
visited[cur] = 0
if cur==K:
return 0
while q:
n = q.popleft()
if n==K: # K에 도달한 값을 출력
return visited[n]
for next_n in (2*n, n-1, n+1): # n+1, n-1, 2*n을 모두 시행해보고 조건에 부합하면 q에 더해준다.
if 0 <= next_n < MAXRANGE and visited[next_n]==-1 and next_n == 2*n: # 방문한적이 없는지, 범위내에 존재하는지 확인한다.
q.append(next_n)
visited[next_n] = visited[n]
elif 0 <= next_n < MAXRANGE and visited[next_n]==-1 and next_n != 2*n:
q.append(next_n)
visited[next_n] = visited[n] +1제출 코드
import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
MAXRANGE = 100001 # N, K의 최대 범위가 100000이다
visited = [-1 for _ in range(MAXRANGE)] # 중복으로 q에 값이 들어감을 방지하고 시간을 체크해주는 배열이다.
def bfs(cur):
q = deque([])
q.append(cur) # q에 초기값을 넣어준다.
visited[cur] = 0
if cur==K:
return 0
while q:
n = q.popleft()
if n==K: # K에 도달한 값을 출력
return visited[n]
for next_n in (2*n, n-1, n+1): # n+1, n-1, 2*n을 모두 시행해보고 조건에 부합하면 q에 더해준다.
if 0 <= next_n < MAXRANGE and visited[next_n]==-1 and next_n == 2*n: # 방문한적이 없는지, 범위내에 존재하는지 확인한다.
q.append(next_n)
visited[next_n] = visited[n]
elif 0 <= next_n < MAXRANGE and visited[next_n]==-1 and next_n != 2*n:
q.append(next_n)
visited[next_n] = visited[n] +1
print(bfs(N))
