백준 5719 문제 링크: https://www.acmicpc.net/problem/5719
📑 문제 설명
1. 거의 최단 경로 찾기
- 거의 최단 경로: 최단 경로에 포함되지 않는 도로로만 이어진 경로 중 가장 짧은 경로를 의미한다.
입력:
첫번째 줄 N, M: 장소의 수, 도로의 수(edge)
두번째 줄 S, D: 시작점, 도착점
세번째 줄부터 U, V, P: U에서 V로 가는 도로의 길이가 P
- U에서 V로 가는 도로는 최대 1개
- U --> V와 V --> U는 다른 도로
입력 마지막 줄에는 0 0 이 주어짐 --> N, M이 0 0이 된다면 프로그램 종료
출력:
각 테스트 케이스에 대해서 거의 최단 경로 길이 출력
- 최단 경로가 없는 경우 -1 출력
💡 문제 해결 방법
알고리즘: 다익스트라 알고리즘
1. 다익스트라 알고리즘을 사용하여 모든 최단 경로를 구한다.
- 다익스트라는 거리 또는 값을 저장하는 배열을 따로 만들고 탐색을 할 때마다 cost or dist가 적으면 값을 교체한다.
- 이 문제를 풀기 위해서는 첫번째 다익스트라 알고리즘에서 모든 최단경로를 구해야 한다.
- 여기서 메모리 초과가 날 수 있다. 왜냐하면 모든 노드를 확인하기 때문이다. 따라서 탐색을 진행하기 전에 내가 지금까지 계산해 cost와 cost를 저장하는 배열의 cost를 비교하여 탐색할 지 말지 정해야 메모리 초과가 안 난다.
- bfs로 역방향 트래킹하여 최단 경로 간선을 지운다. --> 나는 가중치로 사용할 수 없는 값이나 아예 큰 값을 주어 최단 경로 취급을 못하도록 했다.
- 2번에서 간선을 지운 그래프에 다익스트라 알고리즘을 한 번 더 적용하여 거의 최단 경로를 찾는다.
알고리즘 선택 이유
1. 방향성 + 양수 가중치 + 노드 그래프
예외처리 및 추가 내용
1. 다익스트라 알고리즘으로 최단 경로 찾기
2. 최단 경로에 포함된 도로는 사용 금지
3. 찾은 최단 경로의 도로를 제거하고 최단 경로 찾기
4. 3번의 허점은 최단 경로는 1개 이상이기 때문에 여러 최단 경로 중 공유해서 사용하는 도로가 존재함. 첫 번째로 발견한 최단 경로의 도로를 제거할 경우, 두번째 최단 경로가 제거된 도로를 사용할 수 없기 때문에 두번째로 발견된 최단 경로는 최단 경로로 판명나지 못함 --> 이렇게 되면 제거되야 할 도로가 남아있기 때문에 거의 최단 경로에서 사용하게 되어 오류가 발생함
💻 코드
import sys
from collections import deque
def dijkstra(graph, costlist, s):
minload = [[]for x in range(n)]
queue = deque([(s, 0)])
costlist[s] = 0
while queue:
# print("queue", queue)
node, cost = queue.popleft()
if cost > costlist[node]:
continue
for nnode, ncost in graph[node]:
if ncost != -1:
if costlist[nnode] > costlist[node] + ncost:
costlist[nnode] = costlist[node]+ncost
minload[nnode].clear()
minload[nnode].append(node)
queue.append((nnode, ncost))
# print("update", node, nnode, minload)
elif costlist[nnode] == costlist[node] + ncost:
minload[nnode].append(node)
# print("add", node, nnode, minload)
# print(minload)
return minload
def bfs(d, minload, visit, graph):
queue = deque([d])
visit[d] = True
while queue:
node = queue.popleft()
for nnode in minload[node]: # node: 도착, nnode: 출발
if visit[nnode]==False:
queue.append(nnode)
visit[nnode]=True
for index in range(len(graph[nnode])):
if graph[nnode][index][0] == node:
graph[nnode][index][1] = -1
return graph
while True:
n, m = map(int, sys.stdin.readline().split())
if n == 0 and m == 0:
exit()
graph = [[]for x in range(n)]
s, d = map(int, sys.stdin.readline().split())
for i in range(m):
u, v, p = map(int, sys.stdin.readline().split())
graph[u].append([v, p])
costlist = [1e10 for x in range(n)]
# 최단 경로 구하기
minload = dijkstra(graph, costlist, s)
# 최단 경로 제거
visit = [False for x in range(n)]
bfs(d, minload, visit, graph)
# 거의 최단 경로 구하기
costlist = [1e10 for x in range(n)]
dijkstra(graph, costlist, s)
if costlist[d] == 1e10:
print(-1)
else:
print(costlist[d])
💟 추가적으로 알게 된 점
1. 다익스트라 알고리즘 구현 시 탐색할 노드를 결정하는 방법을 알았다. DFS, BFS는 VISIT 배열로 방문 여부를 처리한다면 다익스트라는 (현재 내가 방문할 곳, 그리고 지금까지의 코스트)가 이미 저장된 "현재 방문할 곳의 코스트"보다 클 경우에는 방문하지 않는다. --> 이거 처리 안해주면 메모리 OR 시간 초과 남
2. QUEUE를 사용하여 구현하는 알고리즘에서는 무작정 넣다보면 메모리 OR 시간초과가 나기 때문에 빠진 옵션이 없는지 반드시 체크해야 한다.
