[Python 파이썬] 백준 1504번 - 특정한 최단 경로

2024년 6월 7일

문제 링크 : 백준 1504번 - 특정한 최단 경로

 

---

 

문제

 

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

알고리즘 분류

• 그래프 이론
• 데이크스트라
• 최단 경로

---

문제 접근

 

시작점은 1번 정점, 도착점은 N번 정점으로 고정된다.

단, 임의로 주어진 두 정점 v1, v2는 무조건 지나야 한다.

각 간선은 중복해서 이동할 수 있으며, 각 간선은 단방향이고 최단 경로여야 함에 주의한다.

 

문제의 핵심은 위와 같다.

 

시작점과 도착점이 정해져있고, 최단 경로를 구해야 하므로 다익스트라를 활용하면 된다.

하지만, 두 정점 v1, v2를 무조건 지나야 하니 경우의 수는 다음과 같이 2 가지 도출될 수 있다.

 

1 -> v1 -> v2 -> N
1 -> v1, v1 -> v2, v2 -> N

1 -> v2 -> v1 -> N
1 -> v2, v2 -> v1, v1 -> N

 

 

이에 각 경로의 최단거리를 모두 합해본 후, 더 거리가 작은 최단 거리를 출력하면 된다.

 

단, 경로가 존재하지 않으면 -1을 출력해야 한다.

이는 두 경로에 대해 모두 계산할 필요 없이, 1번 정점에서 각 정점까지 모두 갈수 있는지 확인해보면 된다.

1 -> v1, 1 -> v2, 1 -> N 중 무엇 하나 경로가 존재하지 않는다면, 중간 경로인 v1 -> v2, v2 -> v1, v1 or v2 -> N 모두 존재하지 않기 때문이다.

 

따라서, 1번 정점을 시작으로 첫 로직을 돌렸을 때 v1, v2, N까지의 경로 중 하나라도 존재하지 않음이 확인되면 -1을 출력하고 로직을 종료하여 쓸모없는 추가 연산을 방지할 수 있다.

 

---

순서도

 

1. 정점의 개수 N, 간선의 개수 E, 각 간선의 정보를 인접 리스트로 그래프를 입력받는다.

2. 중간에 무조건 거쳐야 하는 두 정점 v1, v2를 입력받는다.

3. 두 가지 경로에 대한 최단 거리를 담을 길이가 2인 배열 min_dis를 선언한다.
각 경로의 초기 거리는 알 수 없으므로 INF로 초기화한다.

4. 두 경로에 대한 최단거리를 계산한다.
만약 1 -> v1 , 1 -> v2, 1 -> N 경로 중 하나라도 존재하지 않으면 -1을 출력하고 로직을 종료한다.

4-1. 1 -> v1 -> v2 -> N 경로의 최단 경로를 계산한다.
1 -> v1 까지의 최단거리, v1 -> v2 까지의 최단거리, v2 -> N 까지의 최단거리를 각각 다익스트라 알고리즘을 활용해 구한 후 더한다.

4-2. 1 -> v2 -> v1 -> N 경로의 최단 경로를 계산한다.
1 -> v2 까지의 최단거리, v2 -> v1 까지의 최단거리, v2 -> N 까지의 최단거리를 각각 다익스트라 알고리즘을 활용해 구한 후 더한다.


5. 두 경로 중 더 짧은 거리를 출력한다.

 

 

---

입력 예제

 

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

 

 

 

출력 예제

 

7

 

---

전체 코드

 

# 1504

import heapq
import sys

input = sys.stdin.readline

def dijkstra(start_v):
    hq = []
    heapq.heappush(hq, [0, start_v])
    distance[start_v] = 0

    while hq:
        now_dis, now_v = heapq.heappop(hq)
        if now_dis > distance[now_v]:
            continue

        for next_v in graph[now_v]:
            next_dis = now_dis + next_v[0]
            if next_dis < distance[next_v[1]]:
                distance[next_v[1]] = next_dis
                heapq.heappush(hq, [next_dis, next_v[1]]) 



if __name__ == "__main__":
    INF = 1000 * 200000 + 1
    
    N, E = map(int, input().split())
    
    graph = [[] for _ in range(N + 1)]

    for _ in range(E):
        _v1, _v2, c = map(int, input().split())
        graph[_v1].append([c, _v2])
        graph[_v2].append([c, _v1])

    v1, v2 = map(int, input().split())

    # 1 -> v1 -> v2 -> N // 1 -> v2 -> v1 -> N
    min_dis = [INF, INF]

    # 1 -> v1, 1 -> v2
    distance = [INF] * (N + 1)
    distance[1] = 0
    dijkstra(1)

    if distance[v1] == INF or distance[v2] == INF or distance[N] == INF:
        print(-1)
        exit(0)
    
    min_dis[0] = distance[v1]
    min_dis[1] = distance[v2]

    # v1 -> v2, v2 -> v1 
    distance = [INF] * (N + 1)
    distance[v1] = 0
    dijkstra(v1)

    min_dis[0] += distance[v2]
    min_dis[1] += distance[v2]

    # v1 -> N
    min_dis[1] += distance[N]

    # v2 -> N
    distance = [INF] * (N + 1)
    distance[v2] = 0
    dijkstra(v2)
    
    min_dis[0] += distance[N]

    print(min(min_dis))

---

풀이 후기

 

1 -> v1 -> 1 -> v2 -> N, 1 -> v2 -> 1 -> v1 -> N, 1 -> v2 -> v1 -> v2 -> N ... 등등 다양한 경로가 존재할 수 있다.

이를 두 가지 큰 경로로 좁힐 수 있음을 깨닫는다면 다익스트라 알고리즘을 최소한으로 사용하여 풀 수 있는 문제였다.