숨바꼭질 3

백준 13549

수빈이가 동생을 찾는 가장 빠른 시간 구하기.

• 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
• 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
• 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
• 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
• 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
  수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

입출력

입력	출력
5 17	2

---

접근 방식

: nx == x*2 일 때에는 visited[nx] = visited[x], nx == x-1 or nx == x+1 일 때에는 visited[nx] = visited[x] + 1 ---> 틀렸습니다.

알게된 점

X-1, X+1을 먼저 하는 것보다는 2*X로 이동할 수 있으면 전부 2*X로 이동시키고, 그 다음 X-1,X+1로 이동시키면 된다. -> 2*X는 appendleft 그리고 visited에서 먼저 선점해야 하므로 2배 이동하는 조건문을 가장 먼저 실행.

코드

from collections import deque
import sys

def bfs(n, k, visited):
    q = deque()
    q.append(n)
    visited[n] = 0

    while q:
        x = q.popleft()

        if x == k:
            print(visited[x]) 
            break

        if 0<=x*2<=100000 and visited[x*2]==-1:
            visited[x*2] = visited[x]
            q.appendleft(x*2)
            
        if 0<=x-1<=100000 and visited[x-1]==-1:
            visited[x-1] = visited[x] + 1
            q.append(x-1)
            
        if 0<=x+1<=100000 and visited[x+1]==-1:
            visited[x+1] = visited[x] + 1
            q.append(x+1)


n, k = map(int, sys.stdin.readline().split())
visited = [-1]*100001 # 방문여부 및 해당 거리까지 걸리는 시간
bfs(n, k, visited)

x*2와 x-1, x+1은 각각 서로 관련이 없으므로 각각 if문.