[BOJ] 백준 12851 숨바꼭질 2 / BFS

이미지를 클릭하면 문제 사이트로 이동합니다.

 

💭 문제 이해

수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다.

이동하는 세 가지의 선택이 동시에 1초 씩 증가하므로 너비 우선 탐색을 선택했다.

 

가장 빠른 시간으로 찾아가는 방법이 총 몇 가지인지도 구해야 하는 것이 포인트이다.

현재 경로까지의 cnt가 다음 경로에도 합산이 되므로 마치 부분적으로 dp 문제와 같은 느낌이 들었다.

 

 

구현 언어: Python

 

 

from collections import deque


def solve():
    global n, k, sec, cnt
    queue = deque()
    queue.append(n)  # 시작점을 먼저 담는다.
    sec[n] = 0
    cnt[n] = 1
    
    while queue:
        now = queue.popleft()
        for next in (now - 1, now + 1, now * 2):
            # 주어진 범위 내에 있고
            if 0 <= next <= 100000:
                # 방문하지 않은 곳일 때,
                if sec[next] == -1:
                    sec[next] = sec[now] + 1
                    cnt[next] = cnt[now]
                    queue.append(next)
                # 방문했던 곳일 때,
                # 이전에 기록된 최소 시간과 동일한 시간으로 도착할 수 있는 경로 추가
                elif sec[next] == sec[now] + 1:
                    cnt[next] += cnt[now]


n, k = map(int, input().split())
sec = [-1] * 100001
cnt = [0] * 100001
solve()
print(sec[k])
print(cnt[k])