백준 12851번 숨바꼭질2

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

12851번: 숨바꼭질 2

BFS를 이용한 숨바꼭질 문제 시리즈 중에 하나이다.

숨바꼭질 시리즈에서 최단 경로를 구하는 문제의 솔루션을 약간 변형을 하였다.

엣지 케이스를 처리하는 로직을 포함하지 않고 제출을 하지 엣지 케이스 때문에 시간초과가 난다는 문제가 있었다.

 

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

n,k = map(int,input().split())

# 엣지 케이스를 위한 if문
if n > k:
    print(n - k)
    print(1)

else:

    visited = [0]*100001
    q = deque()
    q.append((n,[n]))

    count = 0
    Shortest_time = 1e9

    while q:
        a, SP = q.popleft()
        
        # 이미 거쳐온 경로가 현재 최단 경로보다 크면 패스
        if not (len(SP) -1 <= Shortest_time):
            continue

        if a == k:
            if len(SP) - 1 <= Shortest_time:
                Shortest_time = len(SP) - 1
                count += 1

        visited[a] = 1

        for each in [2,1,-1]:
            tmp = a
            if each == 2:
                if 0 <= tmp*each <= 100000:
                    if not visited[tmp*each]:
                        q.append((tmp*each,SP + [tmp*each]))

            else:
                if 0 <= tmp + each <= 100000:
                    if not visited[tmp + each]:
                        q.append((tmp + each,SP +[tmp + each]))

    print(Shortest_time)
    print(count)