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

문제링크

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는 정수이다.

출력

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

예제 입력 1 

5 17

예제 출력 1 

4

 

문제풀이

 

핵심

1. BFS

2. 메모이제이션

 

1. BFS

해당문제를 보고 DP로 풀어도 되겠다고 생각했다.

그러나 DP보다는 BFS가 더 적합하다. 

 

이유는?

DP는 더이상 쪼갤 수 없는 시작위치에서 목표까지 구하는 문제에 유용하다.

하지만 이 문제는 임의의 시작위치에서 임의의 목표위치까지 가는 경우를 탐색하는 것이 핵심이므로 BFS가 더 적합하다.

BFS는 같은 연산횟수를 가진 형제를 먼저 탐색한다.

 

특정위치에서 연산 한번(연산 한번에 1초이므로)으로 갈 수 있는 위치는 -1, +1, *2 이다.

즉 연산은 -1, +1, *2 가 가능하고, N이 주어졌을때 K까지의 최소 연산 횟수를 구하면 된다.

 

2. 메모이제이션

연산횟수 리스트 만들어서 (나의 경우에는 dist = [0] * (MAX + 1))

자식노드 연산횟수는 부모노드 연산횟수에서 +1씩 업데이트

코드

import sys
from collections import deque

input = sys.stdin.readline
N, K = map(int, input().split())
MAX = 10 ** 5
dist = [0] * (MAX + 1) # ★거리(인덱스번호)에 따른 걸린시간 저장, dist[x] = x위치에 오기까지 걸린 시간

def BFS():
    queue = deque()
    queue.append(N)

    while queue:
        cur = queue.popleft()

        # 최단시간 구해야하므로 시간이 지남에 따라 모든 경우의 수 중 
        # K값에 도달한 경우 나오면 리스트 값 바로 출력. => 최단시간
        if cur == K:
            print(dist[K])
            return

        # cur이 5라고 하면 다음 1초동안 갈수 있는 모든 거리의 경우의 수
        # 즉, 4, 6, 10을 next 값으로 큐에 삽입 및 걸린시간정보 업데이트
        for next in (cur-1, cur+1, cur*2):
            if 0 <= next <= MAX and not dist[next]:
                queue.append(next)
                dist[next] = dist[cur] + 1

BFS()