백준-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)을 제대로 이해하지 못한 상태에서 구현하려다 실패
     • 알고리즘 개념을 탄탄히 해야겠다.
     • 그래야 최적화도 수월하게 할 수 있다.
   • 다른 다익스트라 알고리즘도 풀이해보자
     • 4485-녹색 옷 입은 애가 젤다지?
     • 틀렸던 거 또 틀리지 말자… ​​