[BOJ] 12851. 숨바꼭질2(python)

📌문제

💪아이디어

1. 최소힙을 사용한 bfs
   시간을 노드로 최소힙을 queue로 사용하면 가장 적게 걸린 시간이 먼저 나온다.
   이 문제는 어떻게 움직이든(x+1, x-1, 2*x) time+1이기때문에 굳이 최소힙을 사용하지 않고 deque를 사용해도 된다.
   

2. 가장 적게 걸린 시간 구하기
   pop된 현재 위치가 동생의 위치(K)라면 가장 적게 걸린 시간이다.
   

3. 가장 적게 걸린 시간에 방문 횟수 구하기
   먼저 가장 적게 걸린 시간을 구했는지를 체크한다.
   이전에 시간을 구했고 현재 시간이 그 시간보다 크다면 확인할 필요가 없다.
   최소힙으로 구성되었기 때문에 현재시간이 최소시간보다 작을 수는 없다.
   현재 시간과 최소시간이 같고 현재위치가 동생의 위치라면 방문 횟수를 ++해준다.
   

4. 방문체크
   visited를 통해서 방문할 위치를 체크하였다. 범위가 0에서 100000까지이기 때문에 해당 위치의 방문여부와 범위체크를 해준다.
   동생의 위치는 이전에 방문했어도 방문횟수를 구해야하기 때문에 visited[K] 상태를 변경시키지 않는다. 이를 제외하면 일반적인 bfs문제와 같다.
   

🥂코드

import sys;input = sys.stdin.readline
from heapq import heappush, heappop

N, K = map(int, input().split())
answer = -1
cnt = 0

def bfs():
    global answer, cnt
    queue = []
    visited = [False] * (100001)
    queue.append((0, N))
    visited[N] = True

    while queue:
        time, cur = heappop(queue)
        if answer != -1 and time > answer:
            return
        if cur == K:
            answer = time
            cnt += 1
            continue
        visited[cur] = True
        for nxt in [cur + 1, cur - 1, 2 * cur]:
            if 0 <= nxt < 100001 and not visited[nxt]:
                heappush(queue, (time + 1, nxt))

bfs()
print(answer)
print(cnt)