[Python] 백준 1697 - 숨바꼭질

Baekjoon_1697 - 숨바꼭질

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

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

---

해결방법

• 노드 X가 노드 X-1, X+1, 2X 와 연결되어 있고 또 각각의 노드가 +1, -1, *2 의 노드와 연결되어 있다고 가정하고 BFS 로 탐색한다.

• check 배열의 길이를 갈 수 있는 점의 최댓값으로 잡고, 이동하는 위치의 배열값에 걸린 시간을 누적하면서 x가 k와 같아질때 까지 탐색을 반복한다.

코드

from collections import deque

n,k = map(int, input().split())
check = [0 for i in range(100001)]

def bfs():
    d = deque()
    d.append(n)

    while d:
        x = d.popleft()
        if x == k:
            return check[x]
        for i in (x-1, x+1, 2*x):
            if 0 <= i <= 100000 and not check[i]:
                check[i] = check[x] + 1
                d.append(i)

print(bfs())

check 배열을 단순히 탐색 여부를 알려주는 용도로만 사용하지 않고, 걸린 시간이라는 정보를 담아 활용하는 방법을 생각해내야 하는 문제였다.