[백준 13549] 숨바꼭질 3 (with Python / BFS)

문제링크

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

문제설명

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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

문제풀이

숨바꼭질 문제처럼 BFS 이용하면 된다.

 

핵심

- dist 리스트는 최단시간정보를 저장. (각 인덱스는 거리를 의미한다)

- 순간이동의 비용이 0 이다.

- 즉, 방문한 노드일 경우 최단시간정보를 비교하여 최솟값 갱신할 필요가 있다.

  (이전 숨바꼭질1 , 숨바꼭질2와 다른점)

 

코드

from collections import deque
N, K = map(int, input().split())
M = 100000
dist = [-1] * (M+1) # 해당 인덱스는 거리를 의미, 원소값으로 최단시간정보 저장.

def BFS(start):
    queue = deque([start])
    dist[start] = 0

    while queue:
        cur = queue.popleft()

        for next in (cur-1, cur+1, cur*2):
            if 0 <= next <= M:
                # 방문체크, 방문 안한노드라면
                if dist[next] == -1:
                    queue.append(next)
                    # 순간이동한 경우
                    if next == cur*2:
                        dist[next] = dist[cur]
                    else:
                        dist[next] = dist[cur] + 1
                # 방문한 노드라면
                else:
                    if next == cur*2:
                        dist[next] = min(dist[cur], dist[next])
                    else:
                        dist[next] = min(dist[cur]+1, dist[next])

BFS(N)
print(dist[K])
# 동생을 찾을 수 있는 가장 빠른 시간 찾는 문제