✅ BOJ 12851 - BFS 가짓 수 누적

문제 - 숨바꼭질 2

수빈이가 걷거나 순간이동해서 동생한테 가야 함. 최소 시간으로 도착하는 경우의 수까지 구해야 함.

• 걷기: -1, +1
• 순간이동: *2

순간이동만 무조건 빠르다는 보장 없음. 뒤로 갔다가 순간이동이 더 빠를 수도 있음. 그래서 전부 동시에 봐야 함.

 

전략

최단 시간에 동생 찾는 건 쉬움. 문제는 경로 가짓수까지 세야 한다는 거.

순간이동만 하면 빠르다고 생각하면 바로 틀린다. 뒤로 갔다가 순간이동해서 더 빨라질 수도 있기 때문.

 

이런 문제는 무조건 BFS다. 한 칸 앞으로, 뒤로, 2배 이동 전부 같은 비용이라 레벨 탐색으로 다 같이 봐야 한다.

한 번 방문했다고 끝나는 게 아님. 같은 위치에 같은 시간으로 여러 번 갈 수 있으면 그게 전부 최단 경로임.

그래서 visited는 시간 기록용, cnt는 그 시간에 도착하는 경로 수 누적용으로 사용함.

 

처음 방문하면 cnt[next] = cnt[current]로 이전까지 경로 수 그대로 넘긴다.

이미 방문한 자리라도 같은 시간으로 또 가면 cnt[next] += cnt[current]로 더한다.

DFS 쓰면 모든 경로 끝까지 봐야 해서 시간 터짐.

 

핵심은 visited랑 cnt 둘 다 제대로 쓰는 거. 안 그러면 시간은 맞고 가짓수는 틀림.

---

#bfs
#최단 시간, 경로 수
from collections import deque
import sys
input=sys.stdin.readline

def bfs(start,end):
    limit=10**5+1
    #최단경로 시간
    visited=[-1]*limit
    visited[start]=0
    #최단경로 가짓수
    cnt=[0]*limit
    cnt[start]=1
    q=deque([start])
    
    while q:
        current=q.popleft()
        
        for next in [current-1,current+1,current*2]:
            if 0<=next<limit:
                if visited[next]==-1:
                    visited[next]=visited[current]+1
                    cnt[next]=cnt[current]
                    q.append(next)
                #이미 방문했는데, 같은 시간으로 또 도착할 수 있는 경우 최단경로 추가
                elif visited[next]==visited[current]+1:
                    cnt[next]+=cnt[current]
    
    return visited[end],cnt[end]

def main():
    n,k=map(int,input().split())
    t,c=bfs(n,k)
    print(t)
    print(c)
  
if __name__=="__main__":
    main()