ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Python 3] BOJ - 5719 "거의 최단 경로"
    BOJ 2021. 10. 19. 22:30

     # 문제 링크

    https://www.acmicpc.net/problem/5719

     

    5719번: 거의 최단 경로

    입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있

    www.acmicpc.net

     

     # 풀이

     개인적으로 이 문제의 핵심은 다익스트라와 인접 리스트를 역순으로 뒤집는 것이라 생각한다. 시작점에서 출발하여 끝점까지의 최단 경로는 여러 개 존재할 수 있기 때문에 실제 최단 경로를 찾으려 들면 시간초과를 피할 수 없을 것이다. 그런데 최단 경로라는 점을 생각했을 때 최단 경로 상에 있는 간선의 가중치의 합은 곧 끝점의 최단 거리와 같다. 

    <그림 1. 예제 1의 첫번째 TC>

     위 그림 1에서는 원래 인접 리스트의 방향이 반대인 역인접 리스트와 시작점에서 출발하여 각 점까지의 최단 거리 배열을 나타내고 있다. 이 때 임의의 한 점과 연결된 간선들 중에서 최단 경로 상의 간선을 찾는 방법은 임의의 한 점과 간선으로 연결된 정점의 최단거리에서 현재점까지의 거리의 차이가 간선의 길이와 일치 여부로 알 수 있다. 

     예를 들어 위 그림 1에서 현재점이 6이라고 하자. 따라서, 6과 연결된 정점들은 2,3,4,5이다. 그런데 (2, 6)의 간선의 경우는 만약에 이 간선이 정말로 최단 경로 상의 간선이었다면 현재 D[2]에서 간선의 가중치인 4를 더한 5가 D[6]과 같아야 한다. 그런데 그렇지 않으므로 (2, 6)의 간선은 절대로 최단 경로 상의 간선이 될 수 없음은 자명하다. 이 논리에 의해 (3, 6), (5, 6)의 간선이 최단 경로 상의 간선임을 알 수 있다. 이렇게 계속 최단 경로 상의 간선을 탐색하다가 연결된 정점이 시작점이라면 탐색을 종료한다.

     위 작업이 끝나고 나면 최단 경로 상의 간선을 모두 지울 수 있고 지워진 간선들로 시작점에서 끝점까지의 최단 경로를 문제의 요구에 맞게 출력하면 정답을 구할 수 있다.

     

     # 코드

    import heapq, sys
    
    # dijkstra1 : 현재 정점 v에서 출발하여 각 정점의 최단거리를 갱신하는 함수
    def dijstra1(v):
        d[v] = 0
        q = []
        q.append((0, v))
        while q:
            cur_dist, cur = heapq.heappop(q)
            if d[cur] < cur_dist:
                continue
            for (next, next_dist) in adj[cur]:
                # 다익스트라 갱신 조건을 만족하면서 현재 간선이 최단 경로가 아닌 경우
                if next_dist + cur_dist < d[next] and check[cur][next] == False:
                    d[next] = next_dist + cur_dist
                    heapq.heappush(q, (next_dist + cur_dist, next))
    
    # dijkstra2 : 현재 정점 v에서 출발하여 최단 경로 간선을 지우는 함수
    def dijstra2(v):
        q = []
        q.append((d[v], v))
        while q:
            cur_dist, cur = heapq.heappop(q)
            # 현재점이 시작점이면 탐색 종료
            if cur == s:
                continue
            for (past, past_dist) in rev_adj[cur]:
                # 이미 최단 경로라면 탐색 종료
                if check[past][cur] == True:
                    continue
                # 최단 경로 상의 간선인 경우
                if d[past] == d[cur] - past_dist:
                    check[past][cur] = True
                    heapq.heappush(q, (d[past], past))
    
    INF = 9876543210
    while True:
        # 입력부
        n, m = map(int, sys.stdin.readline().split())
        if n == 0 and m == 0:
            break
        s, e = map(int, sys.stdin.readline().split())
        
        # adj : 일반적 인접리스트
        # rev_adj : 방향을 바꾼 역인접리스트
        adj = [[] for _ in range(n)]
        rev_adj = [[] for _ in range(n)]
        # check : (i, j)를 잇는 간선이 최단 경로 상에 있는 간선인지 아닌지 나타내는 2차원 배열
        check = [[False] * n for _ in range(n)]
        
        # d : 시작점에서 출발하여 각 점의 최단거리를 저장하는 배열
        d = [INF] * n
        for i in range(m):
            a, b, c = map(int, sys.stdin.readline().split())
            adj[a].append((b, c))
            rev_adj[b].append((a, c))
        # 첫 다익스트라1로 d 갱신
        dijstra1(s)
        # 이후 다익스트라2로 check 갱신
        dijstra2(e)
        
        # 거리 배열 초기화 후 두번째 다익스트라로 최단 경로 상의 간선을 배제한 최단 경로 갱신
        for i in range(n):
            d[i] = INF
        dijstra1(s)
        
        # 문제의 조건에 따라 정답 출력
        print(d[e] if d[e] != INF else -1)

    댓글

Designed by Tistory.