[백준] 12851 숨바꼭질2 #bfs

1. 풀이

visit 리스트를 갱신을 queue에서 pop된 다음 해주면 된다.

그렇게 하면 x위치까지 최단시간에 도착하는 경로의 수 만큼 큐에서 pop이 된다.

그러니까 임의의 위치까지 가는 최단경로(최단시간)는 q에 계속 보존이 된다.

 

일반적인 bfs문제처럼 조건확인후 아래와 같이

visited[loc]==-1일때 visited[loc]=visited[loc+x]+1 

하면 처음으로 찾은 최단경로 외에 다른 최단경로는 q에 안들어간다. 

 

2. 소스코드

from collections import deque

maxNum=100000
N,K=map(int,input().split())

visited=[-1 for i in range(maxNum+1)]
q=deque([(N,0)])
case=0

T=maxNum+1
while(q):
    loc,t=q.popleft()
    print(loc,t)
    if t>T:
        break

    if visited[loc]==-1:
        visited[loc]=t

    if loc==K:
        T=t
        case+=1
        continue

    #걷기
    if loc+1<=maxNum and visited[loc+1]==-1:
            q.append((loc+1,t+1))
    if loc-1>=0 and visited[loc-1]==-1:
            q.append((loc-1,t+1))
    #순간이동
    if 2*loc<=maxNum and visited[2*loc]==-1:
            q.append((2*loc,t+1))

print(T)
print(case)