[Python3] 5719 거의 최단 경로 - 플래티넘 5

• 2022.4.25 포스팅 기준 solved.ac 문제 등급 : 플래티넘 5 
• 단계별로 풀어보기 -> 다익스트라
• 알고리즘 분류
  • 그래프 이론
  • 그래프 탐색
  • 다익스트라

 

<링크>
https://www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

시간제한	메모리제한
1 초	256 MB

 

---

<문제>
요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

 

<입력>
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 103) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

 

<출력>
각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

 

<예제 입력 1>

7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0

<예제 출력 1>

5
-1
6

 

---

<풀이 접근>

문제를 해결하는데에 아래와 같은 정보가 필요합니다.

1. 최단경로와 그 경로의 비용
2. 최단경로에 포함되는 도로(간선)의 정보

이 문제에서는 가능한 모든 최단경로에 포함되는 간선을 제외한 후 다시 최단경로를 구하고, 그 비용을 출력해야 합니다. 이를 위해 출발지 노드부터 다익스트라 알고리즘을 수행하는데, 어떤 새로운 간선을 포함하는 것이 최단경로인 경우에만 이 간선을 해당 노드의 최단경로 간선리스트에 저장합니다. 단, 비용이 더 작은 최단경로가 발견되면 기존의 것을 버리고, 새로운 최단경로 간선리스트를 저장합니다. 이 작업을 목적지 노드까지 수행하면, 목적지 노드의 가능한 모든 최단경로들과 그에 포함되는 간선들이 무엇인지 알 수 있습니다.

자세한 설명은 아래의 코드를 참고하시길 바랍니다.

import sys
import heapq
input = sys.stdin.readline
INF = float("inf")


#  while문을 이용한 BFS 방식으로 시작노드 s부터 다익스트라 알고리즘을 수행합니다.
# 이미 처리한 노드를 여러번 다시 방문하지 않기 위해 visited리스트를 사용해 각 노드의 방문 여부를 체크합니다.
def dijkstra(n, s):
    stage = [(0, s)]
    visited = [False for _ in range(n)]
    while stage:
        cost, node = heapq.heappop(stage)
        if visited[node]:
            continue
        visited[node] = True
        for i in available[node]:
            if roads[node][i]+cost < path[i]:
                path[i] = roads[node][i] + cost
                if not visited[i]:
                    heapq.heappush(stage, (roads[node][i]+cost, i))
    return


# 목적지 노드 d부터, 각 노드가 목적지인 간선을 역추적하면서 해당 간선이 최단경로에 포함된 간선일 경우 remove_list에 저장하여 삭제대상 목록으로 반환합니다.
def backtrack():
    stage = [d]
    remove_list = set()
    visited = [False for _ in range(n)]
    while stage:
        next_stage = []
        while stage:
            cur = stage.pop()
            if visited[cur]:
                continue
            visited[cur] = True
            for prev, cost in back[cur]:
                if cost + path[prev] == path[cur]:
                    if not visited[prev]:
                        next_stage.append(prev)
                    if (prev, cur, cost) not in remove_list:
                        remove_list.add((prev, cur, cost))
        stage = next_stage
    return remove_list


while True:
    n, m = map(int, input().split())
    if n==m==0:
        break
    # 특정 노드에서 어떤 목적지 노드들로 도로가 연결되어 있는지 저장.
    # ex) available[x] = [1,2,3]; x노드에서 출발하여 1,2,3노드들로 갈 수 있다. 
    available = [set() for _ in range(n)] 
    
    # 시작노드 s부터 다른 노드들로 가는 최단 경로의 비용을 저장.
    path = [INF for _ in range(n)]
    
    # 특정 노드를 목적지로 하는 도로에 어떤 노드들이 출발지로 연결되어 있는지 저장.
    # ex) back[x] = [1,2,3]; x로 향하는 도로가 1,2,3노드로부터 출발한다.
    back = [set() for _ in range(n)] 
    
    # 도로의 정보를 저장. 
    # road[u][v] = c; u에서 v로 가는 도로의 비용이 c이다.
    roads = [[INF]*n for _ in range(n)] 
    
    s, d = map(int, input().split())
    for _ in range(m):
        u, v, p = map(int, input().split())
        available[u].add(v)
        roads[u][v] = p
        back[v].add((u, p))
    path[s] = 0
    dijkstra(n, s) # 다익스트라 수행 후, path가 작성된다.
    rm_list = backtrack() # 삭제 대상 리스트를 반환. back도 작성된다.
    for u, v, p in rm_list:
    	# 삭제대상 도로 road[u][v] = p에 대하여 u에서 v로 가는 모든 정보가 존재한다면,
        # 해당 도로를 쓸 수 없도록 한다.
        if v in available[u]:
            available[u].remove(v)
            roads[u][v] = INF
            back[v].remove((u,p))
	
    # **중요!**
    # 다익스트라를 다시 수행하기 전에 최단경로 비용을 반드시 초기화해야 합니다.
    path = [INF for _ in range(n)]
    dijkstra(n, s)
    # 두 번째 다익스트라를 통해, "거의 최단 경로"를 얻게된다.
    res = path[d]
    if res == INF:
        print(-1)
    else:
        print(res)

 

위 코드를 제출한 결과는 아래와 같습니다.

Python3 정답 코드들 중 빠른 것은 300ms 전후를 기록합니다.

---

<마무리>

문제를 풀면서 크게 어려운 점은 없었지만, 두 번째 다익스트라 알고리즘을 수행하기 전에 최단경로 비용을 저장한 리스트 path를 초기화 해야 함을 간과해 시간을 많이 낭비했습니다. 

문제의 조건과 그에 따른 요구사항을 정확하게 파악하는 것이 중요함을 상기시켜준 문제입니다.