이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 그래프를 양방향 인접 리스트로 저장하였고, 방문한 곳을 다시 방문하지 않도록 방문 처리도 적용하였다. BFS에 사용할 큐 q는 최소힙으로 구현하였고 q에는 현재까지 만난 소, 현재 위치를 저장하도록 하였다. 그리고 현재 위치가 목적지와 같을 경우에는 결과를 저장하는 변수를 갱신하도록 하였다.

• n, m을 입력받는다.
• 그래프를 저장할 리스트 graph를 2차원 리스트로 선언한다.
• m번 반복하는 for문을 돌린다.
  -> a, b, c를 입력받는다.
  -> graph[a]에 (b, c)를 넣는다.
  -> graph[b]에 (a, c)를 넣는다.
• 결과를 저장할 변수 result를 sys.maxsize로 선언한다.
• 방문 처리 리스트 visited를 False n+1개로 채운다.
• BFS에 사용할 큐 q를 최소힙으로 선언하고 (0, 1)을 넣는다. (0은 여태까지 만난 소의 수, 1은 현재 위치)
• q가 있을 동안 반복하는 while문을 돌린다.
  -> cow, cur을 q에서 추출한다.
  -> 만약 cur이 n과 같을 경우, result를 result와 cow 중 더 작은 수로 갱신하고 종료한다.
  -> 만약 cur이 방문하지 않은 곳이라면,
  --> visited[cur]을 True로 갱신하여 방문처리한다.
  --> graph[cur]을 순회하는 nxt, c_i에 대한 for문을 돌린다.
  ---> tmp에 cow+c_i를 저장한다.
  ---> q에 (tmp, nxt)를 넣는다.
• result를 출력한다.

Code

import sys
import heapq
n, m=map(int, input().split())
graph=[[] for _ in range(n+1)]
for _ in range(m):
    a, b, c=map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
result=sys.maxsize
visited=[False for _ in range(n+1)]
q=[]
heapq.heappush(q, (0, 1))
while q:
    cow, cur=heapq.heappop(q)
    if cur==n:
        result=min(result, cow)
        break
    if not visited[cur]:
        visited[cur]=True
        for nxt, c_i in graph[cur]:
            tmp=cow+c_i
            heapq.heappush(q, (tmp, nxt))
print(result)