남궁찬

질문이나 피드백 감사합니다.

백준-1753-최단경로

업데이트:

문제

최단경로

풀이

  1. 문제조건 해석

    기본적인 최단경로 문제이다.

    최단경로 문제 중 단일 출발 최단경로 문제이다.

    • 단일 노드 u에서 그래프 내 모든 노드에 도착하는 가장 짧은 경로를 찾는 문제
    • 다익스트라, 벨만-포드 알고리즘이 대표적이다.

  2. 알고리즘

    • 다익스트라 알고리즘으로 해결하려고 시도했다.
      • 시작 노드부터 가장 거리가 짧은 노드부터 탐색하면서, 최단거리를 업데이트해야 한다.
        • Optimal Substructure : 최단 경로의 부분 경로는 또한 최단경로이다.
      • 탐색할 노드를 저장할 때, 거리가 짧은 노드부터 접근하려면 우선순위 큐를 사용하는 것이 적합하다
        • 이를 생각해내지 못해서 틀림.
    • 정점 간 여러 간선 있을 수 있다. 최단 거리 간선만 남기도록 한다.

  3. 코드

     from sys import stdin
 import heapq
 input = stdin.readline

 vertex, edge = [int(x) for x in input().rstrip().split()]
 k = int(input().rstrip())
 adj = [dict() for _ in range(vertex+1)]
 for _ in range(edge):
     u, v, w = [int(x) for x in input().rstrip().split()]
     # 정점 간 여러 간선 있을 수 있음
     if v in adj[u]:
         adj[u][v] = min(adj[u][v], w)
     else:
         adj[u][v] = w

 INF = 10*300000+1
 # 다익스트라 최단경로 알고리즘
 def dijkstra(adj, k):
     dist = [INF for _ in range(len(adj))]
     dist[k] = 0

     # 우선순위 큐를 이용해 가장 짧은 경로를 가진 노드부터 방문한다.
     pq = []
     heapq.heappush(pq, (dist[k], k))
     while pq:
         _, u = heapq.heappop(pq)
         if dist[u] < _: 
             # 최적화
             # 큐에 넣었던 경로보다 더 짧은 경로로 업데이트되었을 경우
             continue
         # 인접한 노드에 대해서
         for v, w in adj[u].items():
             # 더 짧은 경로가 발견되었을 때
             if dist[v] > dist[u]+w:
                 # 최단 경로 업데이트하고
                 dist[v] = dist[u]+w
                 # 이후 방문할 노드로 지정
                 heapq.heappush(pq, (dist[v], v))
        
     return dist[1:]

 for i in dijkstra(adj, k):
     if i < INF:
         print(i)
     else:
         print('INF')

  4. 배운점

    • 다익스트라 알고리즘의 핵심 개념(Optimal Substructure)을 제대로 이해하지 못한 상태에서 구현하려다 실패
      • 알고리즘 개념을 탄탄히 해야겠다.
      • 그래야 최적화도 수월하게 할 수 있다.
    • 다른 다익스트라 알고리즘도 풀이해보자

댓글남기기

참고