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

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

12851번: 숨바꼭질 2

---

💡IDEA

BFS를 사용하는 문제이다.

1697번 숨바꼭질 문제와 유사한데, 수빈이가 동생을 찾는 가장 빠른 시간 뿐만 아니라, 가장 빠른 시간으로 찾는 방법의 개수도 구해야 한다.

조심해야 할 점은 방문 처리 부분이다.

예를 들어, 1에서 2로 변했다면 +1을 했을 수도 있고, *2를 했을수도 있어서 append 시에 방문 처리를 해주면 +1로 간 방법과 *2로 간 방법이 같다고 처리되어 방법의 개수를 찾는데 혼선이 있을 수 있다.

따라서, pop 시에 방문 처리를 해주는 것이 적절하다.

 

📌CODE

from collections import deque

N, K = map(int, input().split())
ans = 100000
cnt = 0

def solve(n):
    global ans, cnt
    q = deque()
    q.append((n, 0))
    v = [0]*100001
    while q:
        now, d = q.popleft()
        v[now] = 1
        if now == K and ans >= d:
            ans = d
            cnt += 1
        for nc in [now-1, now+1, now*2]:
            if 0<=nc<=100000 and not v[nc]:
                q.append((nc, d+1))

solve(N)
print(ans)
print(cnt)