[BOJ/1504] 특정한 최단 경로 - 풀이 및 코드

1504번: 특정한 최단 경로

문제

풀이

 1번 노드부터 N번 노드까지의 최단 경로를 구하는 문제입니다. 단, 주어지는 v1, v2 노드를 중간에 반드시 방문해야하는 문제입니다. 노드의 수가 800개 이하이기 때문에 O(N^2)의 알고리즘으로 풀 수 있습니다. 또, 주어지는 간선의 가중치들은 모두 1000 이하의 자연수 라는 조건이 존재합니다.

 

 문제 조건 중, 한 번 지나간 간선이나 정점을 다시 방문할 수 있다는 조건이 있기 때문에 다음과 같이 접근할 수 있습니다.

1. 1번 노드부터 v1 노드까지 최소 비용을 구한다.
2. v1 노드부터 v2 노드까지 최소 비용을 구한다.
3. v2 노드 부터 N번 노드까지 최소 비용을 구한다.
4. 위 세 비용을 합한 것이 답이 된다.

 그러나, 위 경우와 1번 -> v2 노드 -> v1 노드 -> N번 노드의 최소 비용이 다를 수 있기 때문에 두 가지 모두 구하고 둘 중 더 작은 것을 구해줍니다. 또한, 문제의 출력 조건 중 "그러한 경로가 없을 때에는 -1을 출력한다."라는 조건이 존재하기 때문에 최종적인 접근 방법은 다음과 같습니다.

0. 최소 비용은 다익스트라 알고리즘을 통해 구한다.

1. 1번 노드부터 v1 노드까지 최소 비용을 구한다.
2. v1 노드부터 v2 노드까지 최소 비용을 구한다.
3. v2 노드 부터 N번 노드까지 최소 비용을 구한다.
4. 위 세 비용의 합을 ans1이라고 칭한다.

1. 1번 노드부터 v2 노드까지 최소 비용을 구한다.
2. v2 노드부터 v1 노드까지 최소 비용을 구한다.
3. v1 노드 부터 N번 노드까지 최소 비용을 구한다.
4. 위 세 비용의 합을 ans2이라고 칭한다.

만약, ans1, ans2 모두 비용을 구성하는 값 중 불가능한 값이 있다면 -1을 출력하고 그게 아니라면 더 작은 값을 출력한다.

 위 접근법에서는 v1 노드와 v2 노드 사이의 최소 비용을 2번 구하지만, 사실은 1번만 구해도 됩니다. v1와 v2가 연결되어있다면 최소 비용이 존재할 것이고, 그 비용은 시작이 v1이든 v2이든 달라지지 않기 때문입니다.

 

 최소 비용을 구하는 부분을 다익스트라 알고리즘을 구현하여 O(N^2) 내에 문제를 풀 수 있습니다. 이 포스팅에선 우선순위 큐를 활용해 문제를 풀어보았습니다. 

코드

저는 위 접근법에서 ans1과 ans2를 따로 분리하지 않고
"1부터 v1, v2 까지의 비용 중 작은 것 + v1 부터 v2까지 + v1, v2 에서 N 까지의 비용 중 작은 것"을 답으로 제출했더니 반례가 존재하여 틀렸습니다. 만약 1부터 v1까지의 비용이 더 작고, v1에서 N까지의 비용이 더 작다면 오류가 발생하기 때문입니다.

 

BOJ 치팅은 사용 제재 대상입니다.

 

import sys
import heapq
INT_MAX = sys.maxsize

input = sys.stdin.readline
n, e = map(int, input().rstrip().split())
graphs = [[] for _ in range(n+1)]

for _ in range(e):
    a, b, c = map(int, input().rstrip().split())
    graphs[a].append([b, c])
    graphs[b].append([a, c])

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


def dijkstra(start, target):
    dists = [INT_MAX for _ in range(n+1)]
    dists[start] = 0

    # 1번부터 Dijkstra 시작
    min_heap = []
    # Min Heap에는 (dist, node number) 삽입
    heapq.heappush(min_heap, (0, start))

    while min_heap:
        curr_dist, curr_node = heapq.heappop(min_heap)
        # 삽입 된 이후 거리가 갱신되었다면 넘어갑니다
        if curr_dist != dists[curr_node]:
            continue
        # 인접한 노드의 거리를 갱신합니다
        for vertex, val in graphs[curr_node]:
            # 현재 노드를 통해 인접 노드로 방문하는 비용이 더 작은 경우에 갱신
            # 갱신되었다면 큐에 삽입
            if curr_dist + val < dists[vertex]:
                dists[vertex] = curr_dist + val
                heapq.heappush(min_heap, (dists[vertex], vertex))

    if dists[target] == INT_MAX:
        return -1
    else:
        return dists[target]


# v1 -> v2로 가는 경우
v1_v2 = dijkstra(v1, v2)
one_v1 = dijkstra(1, v1)
v2_n = dijkstra(v2, n)


# v2 -> v1로 가는 경우
one_v2 = dijkstra(1, v2)
v1_n = dijkstra(v1, n)

ans1 = 0
ans2 = 0
for cost in [one_v1, v1_v2, v2_n]:
    if cost == -1:
        ans1 = INT_MAX
        break
    else:
        ans1 += cost

for cost in [one_v2, v1_v2, v1_n]:
    if cost == -1:
        ans2 = INT_MAX
        break
    else:
        ans2 += cost

ans = min(ans1, ans2)
if ans == INT_MAX:
    print(-1)
else:
    print(ans)