백준 1848번 동굴 탐험

 

문제설명

월드산의 하부에는 동굴로 들어가는 입구가 있는데, 동굴은 터널을 통해 서로 연결되어 있는 여러 개의 작은 방들로 구성되어 있다. 동굴 입구는 탐험의 시작점이 되는 방 (이하 시작방)으로 곧장 연결되어 있다. 각 방을 연결하는 터널은 서로 교차하지 않으며, 두 개의 방을 연결하는 터널은 많아 봐야 하나이다.

"원쌤배 동굴 탐험 대회"가 개최될 예정이다. 대회의 목표는 시작방에서 출발하여 동굴 내부를 달려, 다시 시작방으로 되돌아 와 빠져 나오는 것인데, 그 경로는 참가자가 마음대로 정할 수 있지만 두 가지 조건을 지켜야 한다. 첫째 조건은, 시작방 이외의 방을 최소한 하나는 거쳐야 한다는 것이며, 둘째 조건은, 어떤 방과 터널도 최대 한 번밖에 방문할 수 없다는 것이다. (시작방은 물론 두 번 방문하게 되므로 예외이다.)

유명한 동굴 탐험가 김진영은 대회에 참가하기 위해 오랜 준비를 했고, 동굴을 여러 번 사전 답사하여 동굴 내부 구조를 알아내는 데 성공했다. 각각의 터널에 대해, 그는 그 터널을 가로지르는 데 필요한 시간을 계산했는데, 터널을 어느 방향으로 가로지르느냐에 따라 걸리는 시간이 서로 다른 경우도 있을 수 있다고 한다. 동굴 입구와 시작방 사이에서 소요되는 시간이나, 방 내부에서 이동하는데 필요한 시간은 무시할 수 있을 만했다. 이제 그는 경기의 규칙을 만족시키면서도, 가장 짧은 시간 내에 완주할 수 있는 경로를 찾아내려고 한다. 그를 돕기 위한 프로그램을 작성하라.

입력

첫째 줄에 n과 m이 주어진다. (3 ≤ n ≤ 5000, 3 ≤ m ≤ 10000) 이는 각각 동굴 내부의 방의 개수와, 터널의 개수를 나타낸다.

이어지는 m개의 줄에는 각각 터널의 정보를 제공하는 네 개의 숫자 a, b, c, d가 포함되어 있다. 이것은 a번 방에서 b번 방으로 갈 때는 c의 시간이 걸리고, 반대로 b번 방에서 a번 방으로 갈 때는 d의 시간이 걸린다는 의미이다. (1 ≤a, b ≤ n. a ≠ b. 1 ≤ c, d ≤ 10000)

방의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 방이 시작방이다. 언제나 조건을 만족하는 경로가 하나는 있다고 가정해도 좋다.

출력

동굴 탐험에 소요되는 최소시간을 출력한다.

 

2. 코드

import sys
from heapq import heappush, heappop
from collections import defaultdict

INF = sys.maxsize
input = sys.stdin.readline

def dijkstra(start, graph, dist):
    queue = []
    dist[start] = 0

    for i in range(len(graph[start])):
        cost, des = graph[start][i]  # 출발 노드에서 연결된 노드들의 비용과 목적지 정보를 가져옴
        queue.append((cost, des, des))  # 큐에 비용, 목적지, 목적지 노드 추가
        dist[des] = cost  # 출발 노드에서 목적지 노드까지의 거리를 해당 노드의 값으로 초기화

    # 다익스트라
    while queue:
        cost, vertex, prev = heappop(queue)  # 우선순위 큐에서 가장 작은 비용을 가진 노드를 꺼냄
        if cost != dist[vertex]:  # 이미 더 작은 거리로 갱신된 경우 무시
            continue
        p[vertex] = prev  # 이전 노드 정보를 저장
        for i in graph[vertex]:
            new_cost = cost + i[0]  # 출발 노드에서 목적지 노드까지의 비용 계산
            if dist[i[1]] > new_cost:  # 저장된 거리보다 더 작은 경우 갱신
                dist[i[1]] = new_cost  # 거리 갱신
                heappush(queue, (dist[i[1]], i[1], prev))  # 큐에 새로운 거리 정보 추가 (비용, 목적지, 이전 노드)
# 입력
n, m = map(int, input().split())

# 정 방향 간선 리스트
graph = defaultdict(list)

# 역 방향 간선 리스트
reverse_graph = defaultdict(list)

# 정 방향 거리, 역 방향 거리 초기화
dist = [INF] * n
dist2 = [INF] * n

queue = []

# 이전 노드들 정점들 저장
p = [-1] * n

for _ in range(m):
    a, b, c, d = map(int, input().split())
    a, b = a - 1, b - 1

    # 정 방향 간선과 역 방향 간선 저장.
    graph[a].append((c, b))
    graph[b].append((d, a))

    # 이 때, 가중치를 반대로 저장하여 역 방향 간선 저장.
    reverse_graph[a].append((d, b))
    reverse_graph[b].append((c, a))

# 시작점 에서 출발 하여 다익스트라 시작
dijkstra(0, graph, dist)

ans = INF
# 역방향 그래프에서 0번 노드로 들어오는 모든 간선에 대해 반복
for i in range(len(reverse_graph[0])):
    # 역방향 그래프에서 0번 노드로 들어오는 i번째 간선의 출발 노드
    col = reverse_graph[0][i][1]

    # col로부터 0번 노드까지의 거리(dist2)를 업데이트 이후 col에서 시작하는 최단경로의 시작점 삽입
    heappush(queue, (reverse_graph[0][i][0], col, 0))
    dist2[col] = reverse_graph[0][i][0]
    dist2[0] = 0


    while queue:
        # 현재 큐에서 가장 최단거리인 정점을 꺼냄
        cost, vertex, prev = heappop(queue)

        # 현재 정점이 이미 처리된 적 있으면(=최단거리가 업데이트된 적 있으면) 넘어감
        if cost != dist2[vertex]:
            continue
        # col로부터 시작한 최단경로와 0번 노드에서 시작한 최단경로가 만나는 지점을 찾았으면 해당 최단경로의 길이를 구하고 종료
        if p[vertex] != col:
            ans = min(ans, cost + dist[vertex])
            continue
        # 현재 정점에서 이웃한 정점들을 모두 검사
        for k in reverse_graph[vertex]:
            # 이웃한 정점으로 가는 거리를 업데이트하고, 큐에 삽입
            new_cost = cost + k[0]
            if dist2[k[1]] > new_cost:
                dist2[k[1]] = new_cost
                heappush(queue, (dist2[k[1]], k[1], 0))
        # 현재 정점이 col이면, 0번 노드로부터의 최단거리(dist2[0])는 업데이트되면 안 됨
        if vertex == col:
            dist2[0] = INF

# col로부터 시작한 최단경로와 0번 노드에서 시작한 최단경로가 만나는 지점이 없을 경우, INF 출력
# 하지만 문제에서 '언제나 조건을 만족하는 경로가 하나는 있다고 가정해도 좋다.' 라고 하였다.
print(ans)

 

3. 문제 해결법

1. 정방향 간선 리스트 와 역방향 간선 리스트 만든다.

2. 문제에서 주어지는 입력 대로 정방향 간선 리스트에 삽입 하고, 역방향 간선 리스트에 역으로 삽입 하면 된다.

많이 헷갈리므로 그림을 그리면 헷갈리지 않고 넣을 수 있다.

3.정 방향 에서 다익스트라 를 돌려서 0번 노드(시작점) 최단 경로를 찾아 낸다.

4.역방향 그래프에서 0번 노드로 들어오는 모든 간선에 대해 반복하며, 해당 간선의 출발 노드로부터 0번 노드까지의 거리를 업데이트 하고, 해당 출발 노드에서 시작하는 최단경로의 시작점을 큐에 삽입하자.

5. 큐에서 가장 최단거리인 정점을 꺼내고, 해당 정점이 이미 처리된 적 있으면 넘어가고, 최단경로를 업데이트할 수 있는 정점이면 업데이트하고 큐에 삽입한다.

6.위의 과정을 반복 하면서 역방향 그래프에서 0번 노드로 들어오는 i번째 간선의 출발 노드가 시작한 최단경로가 만나는 지점을 찾았을 때, 해당 최단경로의 길이를 구하고 종료하면 된다.