[BOJ] 1504 특정한 최단 경로 - python

그래프, 최단 경로 문제, 다익스트라 알고리즘

TIP

문제 링크 (opens new window)

문제 요약

1. Given:
   • 무방향성 가중 그래프(Undirected weighted graph)
   • 반드시 거쳐야 하는, 두개의 정점 번호(v1, v2)
2. Constraints:
   • 2 <= N(정점의 개수) <= 800
   • 0 <= E(간선의 개수) <= 200,000
   • 1 <= c(가중치) <= 1,000
   • v1 != v2, v1 != N, v2 != 1
3. Problem:
   • 아래의 두가지 조건을 만족하면서, 1번 정점 에서 N번 정점 으로 이동하는 특정한 최단 경로를 구해라.
     • 조건1. 임의로 주어진 두 정점은 반드시 통과해야 한다.
     • 조건2. 이미 방문한 정점, 이미 거쳤던 간선도 다시 이동할 수 있다.

문제 접근 플로우

1. (문제 제목에서 알 수 있다시피)최단 경로 알고리즘을 사용하는 문제다. 따라서 다익스트라 알고리즘을 활용하여, 문제 해결할 수 있을 것으로 보인다.
2. 최단 경로는 반드시 1번 정점 에서 출발하여 N번 정점 에서 끝난다. 따라서 최단 경로는 아래와 같은 형태이다
   • 최단경로(1~>N) : path: 1 -> .... -> N
3. v1, v2 을 반드시 거쳐야한다. 따라서 최단 경로는 min(path1, path2) 일것
   • path1 : 1 -> ...-> v1 -> ...-> v2 -> ... -> N
   • path2 : 1 -> ...-> v2 -> ...-> v1 -> ... -> N
4. 중복 방문(or 이동)이 가능하다는 조건 덕분에, path1 과 path2 는 다음과 같이 분할 가능하다. 따라서, 전형적인 최단경로 문제로 변형되었다.
   • path1: 최단경로(1~>v1) + 최단경로(v1~>v2) + 최단경로(v2~>N)
   • path2: 최단경로(1~>v2) + 최단경로(v2~>v1) + 최단경로(v1~>N)
5. 예외(경로가 없는 경우)
   • 1~>v1 경로가 없는 경우
   • 1~>v2 경로가 없는 경우
   • 1~>N 경로가 없는 경우

구현

• 다익스트라(dijkstra) 함수를 세번 호출하여, 부분 경로의 최단 경로를 구한다. 그다음 부분 경로를 합하여 path1 과 path2 의 최단 경로 길이를 구한다. 최종적으로 path1 과 path2 중에 짧은 길이를 최단 경로 길이로 결정한다.
• 그래프 표현: 인접 행렬(Adjaacency matrix)로 정점 연결 관계 및 간선 가중치 표현
  • if adj[u][v] == 1404: 연결x
  • else : 연결o
• 다익스트라 구현 : 전형적인 다익스트라 구현과 같음

from sys import stdin
import heapq

input = stdin.readline


def solve(V, E, adj, v1, v2):
    def dijkstra(src):
        dist = [float('inf') for _ in range(V)]
        dist[src] = 0
        pq = []
        heapq.heappush(pq, (dist[src], src))

        while pq:
            cost, here = heapq.heappop(pq)
            if dist[here] < cost:
                continue
            for there in range(V):
                weight = adj[here][there]
                if weight == 1404:
                    continue
                next_dist = cost + weight
                if dist[there] > next_dist:
                    dist[there] = next_dist
                    heapq.heappush(pq, (next_dist, there))

        return dist

    dist_to = dijkstra(0)
    if float('inf') in (dist_to[v1], dist_to[v2], dist_to[V - 1]):
        return -1

    path1 = dist_to[v1] # 0 -> v1
    path2 = dist_to[v2] # 0 -> v2

    dist_to = dijkstra(v1) 
    path1 += dist_to[v2] # v1 -> v2
    path2 += dist_to[V - 1] # v1 -> V-1

    dist_to = dijkstra(v2)
    path1 += dist_to[V - 1]  # path1 : 0->v1->v2->V-1
    path2 += dist_to[v1]     # path2 : 0->v2->v1->V-1

    return min(path1, path2)


def main():
    V, E = map(int, input().split())
    adj = [[1404 for _ in range(V)] for _ in range(V)]

    for _ in range(E):
        a, b, c = map(int, input().split())
        if c < adj[a - 1][b - 1]:
            adj[a - 1][b - 1] = adj[b - 1][a - 1] = c
    v1, v2 = [int(x) - 1 for x in input().split()]

    res = solve(V, E, adj, v1, v2)

    print(res)


main()

TIP

BOJ 제출소스 (opens new window)