백준 9370번 Dijkstra

서론

9370번: 미확인 도착지

기본적인 Dijkstra 알고리즘 문제였습니다. 알고리즘도 알고 있었고 정석적인 방법으로 구하는 데도 성공했는데, 더 잘 짜보고 싶어서 검색하다가 좋은 아이디어를 발견해서 기록합니다.

제한 조건

• 시간제한 - 3초

시간제한은 3초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. 힙을 사용하는 Dijkstra 알고리즘을 사용하므로 O(ElogV)의 시간 복잡도를 가지고, 문제의 조건에서 E=50,000, V=2,000이니 충분합니다. 지난번 Dijkstra 문제에서 nlogn이라는 표현을 썼었는데 더 정확하게 하면 ElogV가 맞습니다. 여기서 E는 edge의 수, V는 vertex의 수입니다. 한 정점을 기준으로 인접 정점들을 탐색하니 edge 번 만큼 탐색을 하게 되고, 그 안에서 다음 인접 정점을 탐색할 때 힙을 사용하니 logV가 됩니다.

• 메모리 제한 - 256MB

메모리 제한은 256MB입니다. 그래프를 탐색하는 문제를 풀다 보니 기본적으로 그래프 자체를 선언하거나, 일반적으로 사용하는 visited나 dist_list, DP 등을 선언하는 데는 메모리 제한이 크게 문제가 되지 않습니다. 하지만 탐색하는 과정에서 이문제에서는 힙을 사용하는데 조건을 제대로 주어서 힙에 너무 많은 데이터가 쌓이지 않게 해야 합니다. 결론적으로는 알고리즘을 잘 짜야 하겠습니다.

Dijkstra

정석적인 방법은 기본적인 Dijkstra 함수를 구현하고 목적지 후보로 가는 최단 경로를 구하고 g, h를 거쳐 가는 최단 경로를 구했을 때 두 개가 같으면 g, h를 거쳐서 최단 경로가 되었기 때문에 목적지 후보가 될 수 있는 것이고, 같지 않으면 후보에서 제외하면 됩니다.

그런데 위에서처럼 하게 되면 Dijkstra 함수를 세 번 사용해야 하고, start->g->h->목적지 후보의 경우나 start->h->g->목적지 후보의 경우를 생각해야 합니다. 하지만 Dijkstra 한 번으로 목적지 후보로의 최단 경로가 g->h, h->g 경로를 지나 왔는지 확인할 방법이 있습니다.

바로 g, h를 포함하는 경로에는 홀수값을 주고 그 외 경로는 모두 짝수 값을 주는 것입니다. 이렇게 되면 목적지 후보의 최단 경로가 홀수인 경우는 g, h 경로를 지나왔다는 소리가 되고 짝수이면 지나오지 않았다는 소리가 됩니다. *2, *2-1을 하더라도 수의 대소관계는 유지된다는 전제가 있기 때문에 가능합니다. 또 *2+1, *2-1을 선택할 때에는 -1을 선택해야 합니다. 만약 g, h를 거치지 않는 경로와 거치는 경로가 값이 같을 때, g, h를 거쳐서도 갈 수 있다는 소리가 되기 때문에 g, h를 먼저 선택해서 마지막 값에 홀수 값이 반영돼야 하기 때문입니다.

전체코드는 아래와 같습니다.

import sys
import heapq
input = sys.stdin.readline


def make_graph(vertex_num, edge_num, target_v1, target_v2):
    graph = {}
    for i in range(1, vertex_num+1):
        graph[i] = []
    for __ in range(edge_num):
        start, end, weight = map(int, input().split())
        if (start == target_v1 and end == target_v2) or (end == target_v1 and start == target_v2):
            graph[start].append([end, weight*2-1])
            graph[end].append([start, weight*2-1])
        else:
            graph[start].append([end, weight*2])
            graph[end].append([start, weight*2])
    return graph


def Dijkstra(start, graph):
    dist_list = [sys.maxsize//2*2] * (vertex_num+1)
    dist_list[start] = 0
    heap = []
    heapq.heappush(heap, [0, start])

    while heap:
        base_dist, base_v = heapq.heappop(heap)
        if base_dist > dist_list[base_v]:
            continue
        for next_v, weight in graph[base_v]:
            next_dist = dist_list[base_v]+weight
            if next_dist < dist_list[next_v]:
                dist_list[next_v] = next_dist
                heapq.heappush(heap, [next_dist, next_v])

    return dist_list


tc = int(input())
for __ in range(tc):
    vertex_num, edge_num, dest_num = map(int, input().split())
    start, target_v1, target_v2 = map(int, input().split())
    graph = make_graph(vertex_num, edge_num, target_v1, target_v2)
    dest_list = []
    for i in range(dest_num):
        dest_list.append(int(input()))
    dest_list = sorted(dest_list)

    dist_list = Dijkstra(start, graph)

    for i in dest_list:
        if dist_list[i] % 2 != 0:
            print(i, end=' ')
    print()

생각

대단한 아이디어인 것 같습니다.

*추가

그래프탐색 관련 포스팅을 하면서 node라는 단어와 vertex라는 단어를 혼용해서 쓴 거 같은데 앞으로는 vertex, 정점이라는 단어를 사용하도록 하겠습니다.