📜 문제 이해하기
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
💡 문제 재정의
그래프와 경유정점이 주어질때 1번부터 N번 정점으로 경유지를 지나는 최단 경로를 구하시오.
✏️ 계획 수립
경로가 2개밖에 없으므로 항상 두 가지 경로로 나타낼 수 잇다.
1) 1 -> v1 -> v2 -> N
2) 1 -> v2 -> v1 -> N
이 문제는 3번의 다익스트라로 문제를 풀 수 있다. 첫번째 다익스트라는 1번부터 v1과 v2까지의 최단 경로를 구한다. 그 다음 두번째 다익스트라 v1부터 시작으로 v1->v2, v2->v1 사이의 거리를 구한다. 두 거리는 같은 거리로 하나의 다익스트라로 구할 수 있다. 또한 v1부터 시작했기때문에 v2->v1->N을 바로 구할 수 있다. 마지막 세번째 다익스트라로 v2부터 시작으로 v1->v2->N을 구할 수 있다. 이 두 path에서의 가장 작은 값을 출력한다.
💻 계획 수행
import sys
import math
status = []
distance = []
tree = []
fringe = []
def get_min_distance_idx():
min_distance = math.inf
min_idx = 0
fringe_idx_ = 0
for f, idx in enumerate(fringe):
if min_distance > distance[idx]:
min_distance = distance[idx]
min_idx = idx
fringe_idx_ = f
return min_idx, fringe_idx_
def dijkstra(start_idx):
global status, distance, tree, fringe
status = ['U' for _ in range(N + 1)]
distance = [math.inf for _ in range(N + 1)]
tree = []
fringe = []
tree.append(start_idx)
status[start_idx] = 'T'
distance[start_idx] = 0
for i, weight in enumerate(graph[start_idx]):
if weight > 0:
fringe.append(i)
status[i] = 'F'
distance[i] = weight
while fringe:
# 가장 가까운 값의 노드를 트리에 추가
next_idx, fringe_idx = get_min_distance_idx()
tree.append(next_idx)
status[next_idx] = 'T'
fringe.pop(fringe_idx)
for i, weight in enumerate(graph[next_idx]):
# 연결된 것들 중에서
if weight > 0:
# fringe에 없다면 update
if status[i] == 'U':
fringe.append(i)
status[i] = 'F'
distance[i] = distance[next_idx] + weight
# 현재 경로보다 더 짧은 경로라면 업데이트
elif status[i] == 'F' and distance[i] > (distance[next_idx] + graph[i][next_idx]):
distance[i] = distance[next_idx] + graph[i][next_idx]
if __name__ == '__main__':
N, E = map(int, sys.stdin.readline().split())
graph = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(E):
node1, node2, edge_weight = map(int, sys.stdin.readline().split())
graph[node1][node2] = edge_weight
graph[node2][node1] = edge_weight
v1, v2 = map(int, sys.stdin.readline().split())
path1_sum = 0
path2_sum = 0
dijkstra(1)
path1_sum += distance[v1]
path2_sum += distance[v2]
dijkstra(v1)
path1_sum += distance[v2]
path2_sum += distance[v2]
path2_sum += distance[N]
dijkstra(v2)
path1_sum += distance[N]
if path1_sum == math.inf and path2_sum == math.inf:
print(-1)
else:
print(min(path1_sum, path2_sum))🤔 회고
처음에는 경유지를 어떻게 할까 고민이었지만 여러 번의 다익스트라로 문제를 풀 수 있음을 알았다. A*를 사용하면 더 빠른 풀이를 제공할 수 있을 것이다.
