[백준 1697] 숨바꼭질 (실버 1) 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는 정수이다.

출력

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

---

풀이

  이 문제와 같이 여러 계산 방식을 이용해 목표 값에 다가가는 문제 유형은 BFS 알고리즘으로 해결할 수 있다. 이 문제의 경우, 현재 위치를 x라고 할 때, 다음으로 갈 수 있는 위치는 2*x, x-1, x+1이다. 이때 2*x, x-1, x+1 를 다음에 방문할 정점으로 삼는다면, BFS는 최단 경로를 보장해주므로 n에서 k까지 갈 수 있는 최단 경로를 구할 수 있다.

# 백준 1697 숨바꼭질 실버1 https://www.acmicpc.net/problem/1697
# 걸음: x에서 1초 후 x-1 또는 x+1로 이동 가능.
# 순간이동: 1초 후 2*x로 이동
# n에서 k로 가는 가장 빠른 시간
from collections import deque
n, k = map(int, input().split())

def bfs(start):
    q = deque([start])
    visited = [0] * 100001
    while q:
        x = q.popleft()
        if x == k:
            return visited[x]
        for i in ([x-1, x+1, 2*x]):
            if -1 < i < 100001 and not visited[i]: 
                visited[i] = visited[x] + 1
                q.append(i)

print(bfs(n))

  문제 조건에서 n과 k가 각각 100000 이내에 있다고 하였으므로, 방문 여부를 저장할 visited 배열도 그만큼의 길이로 미리 만들어준다. BFS 함수에서 다음 방문할 정점을 x-1, x+1, 2*x로 설정해주고, q에서 꺼낸 값이 k가 되면 k까지 도착한 것이므로 결과값을 리턴해준다.