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

12851번 - 숨바꼭질 2

문제 이해

N에서 시작, 한번 이동 시 현재 위치가 x라면 x+1, x-1, x*2로 이동 가능.
K까지의 최단 시간과, 가능한 경로 수를 구해내는 문제.

접근

BFS(Breadth First Search:너비 우선 탐색)를 통헤 최단거리를 구하는데, 이때 거리를 기록하는 동시에 방문 횟수를 기록한다.
한번에 처리하기 위해 2차원 배열을 이용해 풀이했다.

정답 코드

import sys
from collections import deque

N, K = map(int, input().split())
time_count = [[-1, 0] for _ in range(100001)]
# BFS
q = deque([N])
time_count[N] = [0, 1]
while q:
    x = q.popleft()

    for i in [x+1, x-1, x*2]:
        if i < 0 or i > 100000:
            continue

        if time_count[i][0] == -1: # 첫방문 - 거리 기록
            time_count[i] = [*time_count[x]]
            time_count[i][0] += 1
            q.append(i)

        elif time_count[i][0] == time_count[x][0]+1: # 최단경로로 도달한 경우 이전의 경우르 합쳐줌
            time_count[i][1] += time_count[x][1]


print(*time_count[K], sep="\n")