[solved.ac 골드5] 13549_숨바꼭질 3 (파이썬, BFS)

제한 사항

문제

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

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

입력

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

출력

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

예제

---

나의 풀이

2022.05.22 - [solved.ac 골드5] 12851_숨바꼭질 2 (파이썬, BFS)

[solved.ac 골드5] 12851_숨바꼭질 2 (파이썬, BFS)

 

이전에 풀었던 숨바꼭질 2와 비슷하지만 차이점이 있다.

우선 공통점은 동생을 찾을 수 있는 경우가 여러 가지라서 방문 체크를 큐에 넣을 때가 아닌 큐에서 꺼낼 때 한다는 점이다.

차이점은 순간 이동을 할 때 숨바꼭질 2는 1초가 소요되고, 이번 문제인 숨바꼭질 3에서는 0초가 소요된다는 점이다.

숨바꼭질 2의 풀이에서는 큐에 시간 순으로 입력된다는 보장이 있었기 때문에 동생을 찾은 시간이 더 큰 시간이 발견되면 탐색을 종료했지만 이번 문제에서는 큐에 들어가는 (위치, 시간) 중 시간이 커졌다 작아졌다 하기 때문에 끝까지 탐색한다.

동생을 찾은 경우 리스트에 담아뒀다가 마지막에 리스트에서 가장 작은 값만 출력하면 된다.

from collections import deque

n, k = map(int, input().split())
q = deque([(n, 0)])
MAX = 100001
visited = [False] * MAX
answer = []
while q:
    now, time = q.popleft()
    visited[now] = True
    if now == k:
        answer.append(time)
    if now * 2 < MAX and not visited[now * 2]:
        q.append((now * 2, time))
    if now + 1 < MAX and not visited[now + 1]:
        q.append((now + 1, time + 1))
    if now - 1 >= 0 and not visited[now - 1]:
        q.append((now - 1, time + 1))
print(min(answer))

채점 결과