[백준] 12851 숨바꼭질 2 (파이썬 python)

 

 

문제 링크

 

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

12851번: 숨바꼭질 2

 

 

문제 풀이

 

import sys
input = sys.stdin.readline
from collections import deque
n, k = map(int, input().split())
queue = deque([n])
cnt = 0
result = 0
visited = [0] * 100001

while queue:
    now = queue.popleft()
    if now == k:
        result = visited[now]
        cnt += 1
        continue
    for next in (now - 1, now + 1, now * 2):
        if 0 <= next <= 100000 and (not visited[next] or visited[next] == visited[now] + 1):
            visited[next] = visited[now] + 1
            queue.append(next)

print(result)
print(cnt)

 

 

bfs를 통해 풀이했습니다.

단순히, 최소 시간만 구하는 것이 아니라 최소 시간에 대한 경로의 수도 구해야 하는 문제이므로,

방문 처리를 하는 visited 배열에 시간을 함께 저장하여 처리했습니다.

기존에는 not visited[next]라는 조건만 주어 방문했던 곳은 다신 방문하지 않게 했었다면

이 문제에서는 방문했었던 지점이라도 방문한 시간이 같다면 방문할 수 있게하여

다양한 경로의 수를 카운트할 수 있게 했습니다.