[백준_1697] 숨바꼭질_python

https://www.acmicpc.net/problem/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는 정수이다.

출력

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

문제해결

수빈이의 위치에서 동생이 있는 위치까지의 최단거리(시간)을 찾아내는 문제이다.

5라는 숫자에서 시작해 5->(4,6,10) - > ((3,5,8),(5,7,12),(9,11,20))...->... 

+1,-1, *2 의 값이 다음 방문하는 node라고 생각하고 가지치기(트리형태)형태라고 생각하면 될 것 같다.

수빈이의 이동거리를 배열에 넣고 하나씩 뽑아도 되지만 for _ in _ 구조를 사용해 다음 방문위치에 대한 예외 설정을 거치고

q에 담아 bfs(너비우선탐색) 최단거리를 찾는 방식으로 문제를 해결하였다.

dist(distance)의 0으로 초기화 되어있는 배열에 수빈이가 이동한 거리는 인덱스로 나타내고 값은 이동할때마다 +1의 누적값을 담아

동생과 거리(인덱스)가 같아졌을 때 해당 인덱스 값을 출력하도록 코드를 설정하였다.

from collections import deque

n , k = map(int,input().split())
dist = [0]*(100001)
cnt=1
def bfs(x):
    q = deque()
    q.append(x)
    while q :
        next = q.popleft()
        if next == k :
            print(dist[next])
            break
        for nx in(next+1, next-1, next*2):
            if 0 <= nx <= 100000 and not dist[nx]:
                q.append(nx)
                dist[nx]=dist[next]+1
bfs(n)