[탐색/BFS] 백준 12851 숨바꼭질 2 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

12851번: 숨바꼭질 2

 

 

 

2. 문제 풀이

 수빈이는 1초에 x+1, x-1, x*2 만큼 이동할 수 있습니다. 현재 위치에서 동생이 있는 위치로 이동하려면, 최소 몇 초가 필요한지 구해야 합니다.

 

2022.02.24 - [Algorithm] - [탐색/BFS] 백준 1697 숨바꼭질 - Python

[탐색/BFS] 백준 1697 숨바꼭질 - Python

 숨바꼭질 1 문제와 달리, 최단 경로의 개수도 출력해야 합니다.

 

 

 

3. 코드

from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())  #출발 / 도착
dist = [0] * 100001  #최대 0부터 100000까지의 지점까지 걸리는 횟수 기록

# BFS 탐색
queue = deque()
queue.append(N)  # 시작점

cnt = 0  # 최적경로 수
min_path = 0  # 최소 시간

# 큐가 빌 때까지 탐색
while queue:
    x = queue.popleft()
    # 도착지점이라면 탐색 종료
    if x == K:
        min_path = dist[x]
        cnt += 1
        continue

    # x에서 -1 또는 +1 또는 *2 탐색
    for nextX in (x+1, x-1, 2*x):
        # 0~100000지점 내이고, 방문하지 않았거나 동일한 탐색횟수를 가졌으면 탐색
        if 0 <= nextX <= 100000 and (dist[nextX] == 0 or dist[nextX] == dist[x]+1):
            dist[nextX] = dist[x] + 1  # 방문하고 횟수 1늘림
            queue.append(nextX)  # 큐에 추가

# 출력
print(min_path)
print(cnt)

 달라진 점은 '동일한 탐색횟수를 가진 곳'도 탐색한다는 점입니다. 이를 통해, 이미 탐색했던 곳도 포함해서 다양한 최단 경로를 탐색할 수 있습니다. 그렇지 않으면, 앞선 최단 경로가 지나간 경로는 사용할 수 없으므로 모든 경우의 수를 구할 수 없습니다.