[Python] 백준 10917

 

 

어려웠던 문제는 스스로 솔브해도 다른 사람 풀이랑 비교하기 위해서 검색을 해보는데 푼 사람이 별로 없어서 검색해도 안나와서 슬펐당...

내 답이 최적인지는 모르겠으나 일단 풀었고 푼 사람이 별로 없어서 나라도 리뷰를 써놔야지,,😇

 

 

 

 

일단 나는 BFS + 우선순위Q로 풀었다.

딕셔너리를 만들고 x를 key로 y를 value로 두고, value는 우선순위Q 내림차순으로 저장했다.

(꿈은 더 큰 수로 이동하고 N이 가장 크기 때문에 N을 가지고 있다면 바로 그만 할 수 있게하기 위함)

그리고 queue에 현재 위치와 현재 상황이 바뀐 횟수를 저장하며 BFS를 한다.

N을 만나면 그만한다. (bfs니까 처음만날 때 최소)

 

 

Result

import sys
from collections import defaultdict
from collections import deque
import heapq


n,m = map(int, sys.stdin.readline().split())
dic=defaultdict(list)
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    #내림차순으로 heap에 넣음
    heapq.heappush(dic[a],-b)

res = -1
q=deque([[1,0]])
while q:
    num,cnt=q.popleft()
    for i in range(len(dic[num])):
        #내림차순으로 넣었으니까 나올 때 *-1
        temp = -1*heapq.heappop(dic[num])
        if temp == n:
            res=cnt+1
            break
        else:
            q.append([temp,cnt+1])
    if res != -1:
        break
print(res)