BOJ_5719 거의 최단 경로
- TOC {:toc}
이 글은 백준 온라인 저지의 5719번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.
일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.
2021.07.07
틀린 풀이입니다. 정답은 참고 답안을 참고해주세요.
| 단계 | 시작 시각 | 끝난 시각 | 걸린 시간 |
|---|---|---|---|
| 문제 이해 | 23:18:37 | 23:22:21 | |
| 풀이 생각 + 코딩 1 | 15:47:51 | 16:31:12 | |
| 풀이 생각 + 코딩 2 | 20:54:29 | 22:13:41 | |
| 디버깅 | 22:41:36 | 22:55:59 |
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def dijkstra(S, D):
# 출발점에서 각 점까지의 최소 거리를 담는 리스트
# 기존 다익스트라 알고리즘과 다르게 최소 거리뿐만 아니라
# 지금까지 지나온 노드의 리스트를 포함한다.
L = [[float("inf"), []] for _ in range(N)]
L[S][0] = 0
L[S][1] = [S]
heap = [(0, S)]
while heap:
len_n, n = heappop(heap)
for i in range(N):
if road[n][i]:
total = road[n][i] + len_n
if total < L[i][0]:
L[i][0] = total
L[i][1] = L[n][1] + [i]
heappush(heap, (total, i))
return L[D]
while True:
N, M = map(int, input().split())
if not N and not M:
break
S, D = map(int, input().split())
road = [[0] * N for _ in range(N)]
for _ in range(M):
U, V, P = map(int, input().split())
road[U][V] = P
# 최초 다익스트라 알고리즘을 수행한 값.
# 최단 경로의 길이와 그 경로를 이루는 노드의 리스트이다.
min_sec, route = dijkstra(S, D)
while True:
# road에서 route를 이루고 있는 노드들 사이의 간선을 제거한다.
for i in range(len(route) - 1):
road[route[i]][route[i + 1]] = 0
# 다시 다익스트라 알고리즘을 수행한다.
new_min, route = dijkstra(S, D)
# 새로 얻은 최단 경로의 길이가 기존의 값보다 크면
if new_min > min_sec:
# 조건에 따라 출력한 뒤
if new_min == float("inf"):
min_sec = -1
else:
min_sec = new_min
# 반복을 종료한다.
break
print(min_sec)
아이디어 & 풀이
다익스트라 알고리즘을 이용해 최단 거리를 찾는다.
- 일반적인 다익스트라 알고리즘과 다르게 최소거리와 함께 지나온 노드를 리스트로 저장한다.
- 목표 노드(
D)의 지나온 리스트를 순회하면서 해당 경로를 간선 리스트(e.g.,road)에서 제거한다.- 간선 리스트의 가중치 값을 0으로 바꾼다.
- 첫 번째로 구한 최소 거리는 저장해둔다.
위에서 구한 최소 거리(i.e., min_sec)보다 작은 값의 최소 거리를 얻을 때까지 위의 과정을 반복한 다음, 그 값보다 바로 다음으로 큰 시간 값을 출력한다.
디버그
계속 시간 초과가 떴다.
피드백
- 위의 방법으로 풀면 한 번에 한 최단 경로만 저장하게 되기 때문에 최단 경로가 여러 개일 경우 그만큼 다익스트라 알고리즘을 반복해서 실행해야 한다.
- 역방향의 간선 리스트를 저장한 뒤 ‘bfs’를 이용하면 한 번에 모든 최단 경로를 역추적할 수 있었다.
- 역방향 리스트를 생성하고 이전 노드의 최단 거리와 간선 값을 더해서 이용해야 할 것 같았는데 bfs로 경로 전체를 탐색할 생각을 못 했다.
- 목표 노드 직전 노드에만 적용하려고 했음.
- 경로를 제거하는 방식도 효율적이지 못했다.
- 경로를 기존의
(node, dist)꼴의 튜플의 리스트로 구성을 하면 이를 중간에서 찾은 뒤 제거할 때마다 시간이 너무 많이 걸린다. - 그래서 아예 이차원 리스트로 만든 뒤 경로가 없는 경우를 0으로 뒀는데, 이 역시 모든 노드 사이의 관계를 다 순회해야 한다는 점에서 시간이 오래 걸렸다.
- 다음 노드를 key로 사용하는 딕셔너리의 리스트로 만들어서 관리를 해줘야 했다.
- 경로를 기존의
- 참고 답안 1에서
remove_list의 간선을road에서 제거하는 것도bfs()안에 포함하는 것도 괜찮을 것 같다.
참고 답안 1
import sys
from collections import deque
from heapq import heappush, heappop
input = sys.stdin.readline
def dijkstra():
heap = [(0, S)]
distance[S] = 0
while heap:
dist, now = heappop(heap)
if distance[now] < dist:
continue
for i in road[now]:
cost = dist + road[now][i]
if cost < distance[i]:
distance[i] = cost
heappush(heap, (cost, i))
def bfs():
queue = deque([D])
while queue:
now = queue.popleft()
# 출발점을 만나면
if now == S:
# 넘긴다.
# break를 하면 남은 노드를 탐색할 수 없다.
continue
for prev, cost in rev_road[now]:
if distance[prev] + cost == distance[now]:
# 이미 제거되지 않는 경우에만
if (prev, now) not in remove_List:
# 해당 간선을 remove_list에 추가한다.
remove_List.append((prev, now))
queue.append(prev)
while True:
N, M = map(int, input().split())
if N == 0 and M == 0:
break
S, D = map(int, input().split())
# 간선 리스트
road = [{} for _ in range(N)]
# 역방향 간선 리스트
rev_road = [[] for _ in range(N)]
# 간선 리스트 및 역방향 간선 리스트를 구성한다.
for _ in range(M):
U, V, P = map(int, input().split())
road[U][V] = P
rev_road[V].append((U, P))
# 다익스트라 알고리즘을 수행한다.
distance = [float("inf")] * N
dijkstra()
# 최단 경로를 이루는 간선 리스트
remove_List = list()
bfs()
# remove_list의 간선을 road에서 제거한다.
for U, V in remove_List:
del road[U][V]
# 다시 다익스트라 알고리즘을 수행한다.
distance = [float("inf")] * N
dijkstra()
print(distance[D] if distance[D] != float("inf") else -1)
아이디어 & 풀이
다익스트라 알고리즘을 이용해 최단 거리를 찾는다.
- 간선 리스트
road를 딕셔너리의 리스트로 구성한다.- e.g.,
U에서V,W,X로 가는 간선 리스트:road[U] = {V: dist 1, W: dist 2, X: dist 3} - 다음에 간선 제거를 쉽게 하기 위해서이다.
- e.g.,
목표 지점 D부터 bfs를 이용해 최단 경로를 이루는 간선을 road에서 제거한다.
- 이를 위해
road를 구성할 때 역방향 간선 리스트인rev_road도 함께 구성한다.rev_road는 추후 수정할 일이 없기 때문에(prev_node, dist)튜플의 리스트로 구성한다.
rev_road에 따라 노드를 역방향으로 탐색하면서 해당 간선이 최단 경로에 포함되어 있으면 제거한다.- 현재 ‘노드의 최단 거리’가 ‘이전 노드의 최단 거리 + 간선의 거리’와 같으면 최단 경로에 포함된 것이다.
- 최단 경로에 포함된
(이전 노드, 다음 노드)쌍을remove_list에 추가한 뒤, 이후remove_list를 순회하면서road의 딕셔너리값을 제거한다. - 동일한 간선을 포함한 최단 경로가 여러 가지일 수 있기 때문에,
if (prev, now) not in remove_List로 중복으로 간선을 제거하는 것을 방지해주어야 한다.- 기존 bfs의
visitied와 같은 역할.
- 기존 bfs의
- 출발점
S는 이전 노드가 존재하지 않기 때문에continue로 넘긴다.
최단 경로를 이루는 간선을 모두 제거한 road에서 다시 다익스트라 알고리즘을 이용해 찾은 최단 경로의 길이를 출력한다.
참고 답안 2
from heapq import heappush, heappop
from collections import deque
import sys
input = sys.stdin.readline
INF = sys.maxsize
def dijkstra():
heap = [[0, S]]
distance = [INF] * N
distance[S] = 0
while heap:
dist, now = heappop(heap)
if dist > distance[now]:
continue
for next, next_dist in arr[now]:
# 제거된 간선은 넘어간다
if next_dist == -1:
continue
cost = dist + next_dist
if cost < distance[next]:
distance[next] = cost
heappush(heap, (cost, next))
# next가 가리키는 기존의 노드를 모두 제거하고
# now만 남긴다.
rev_arr[next] = [now]
elif cost == distance[next]:
# next가 가리키는 노드에 now를 추가한다.
rev_arr[next].append(now)
return distance
while True:
N, M = map(int, input().split())
if N == 0 and M == 0:
break
S, D = map(int, input().split())
arr = [[] for i in range(N)]
rev_arr = [[] for i in range(N)]
for i in range(M):
U, V, P = map(int, input().split())
arr[U].append([V, P])
dijkstra()
visited = [0] * N
visited[D] = 1
queue = deque([D])
while queue:
now = queue.pop()
# 현재 노드의 이전 노드 prev를 순회하면서
for prev in rev_arr[now]:
for i in range(len(arr[prev])):
# arr에서 prev가 가리키는 다음 노드가 now이면
if arr[prev][i][0] == now:
# 그 간선을 제거한다.
# (길이를 -1로 바꾼다)
arr[prev][i][1] = -1
if not visited[prev]:
visited[prev] = 1
queue.append(prev)
res = dijkstra()
print(-1 if res[D] == INF else res[D])
아이디어 & 풀이
참고 답안 1과 전개는 비슷하지만, 역방향 간선 리스트를 구성하고 해당 간선을 제거하는 과정을 각각 다익스트라와 bfs 안에 포함시켰다.
참고 답안 3
경로 제거를 원 간선 리스트에 직접 하지 않고 다른 리스트를 만들어 관리하는 방식이다. 답안으로 제출하면 역시 시간 초과가 뜨긴 하는데 일단 기록해둔다.
import sys
from heapq import heappush, heappop
from collections import deque
input = sys.stdin.readline
def dijkstra():
heap = [(0, S)]
distance[S] = 0
while heap:
dist, now = heappop(heap)
if distance[now] < dist:
continue
for i in road[now]:
cost = dist + i[1]
# 제거된 간선이 아니라는 조건을 추가한다.
if distance[i[0]] > cost and not dropped[now][i[0]]:
distance[i[0]] = cost
heappush(heap, (cost, i[0]))
def bfs():
queue = deque()
queue.append(D)
while queue:
now = queue.popleft()
if now == S:
continue
for prev, cost in rev_road[now]:
if distance[now] == distance[prev] + cost:
# prev에서 now로 가는 간선을 제거한다.
dropped[prev][now] = True
queue.append(prev)
while True:
N, M = map(int, input().split())
if N == 0:
break
S, D = map(int, input().split())
road = [[] for _ in range(N)]
rev_road = [[] for _ in range(N)]
for _ in range (M):
U, V, P = map(int, input().split())
road[U].append((V, P))
rev_road[V].append((U, P))
# 해당 경로의 제거 여부를 저장하는 리스트
dropped = [[False] * N for _ in range(N)]
distance = [float("inf")] * N
dijkstra()
bfs()
distance = [float("inf")] * N
dijkstra()
if distance[D] != float("inf"):
print(distance[D])
else:
print(-1)
-
ps-python failed