언어를 잘못 설정해서 컴파일 에러가 났다
문제
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
해결 방법
일단 문제를 읽으면서 중요한 키워드가 무엇인지 생각해보았다. 딱 두 가지가 나왔다.
1. 방향성이 없다 => 양방향
2. 임의로 주어진 두 정점은 반드시 통과해야 한다.
이 두가지가 문제를 어렵게 만드는 것이다. 양방향 그래프는 그래프를 만들 때 단방향 그래프를 역으로 추가해주는 방식으로 해결이 된다.(이게 가장 좋은 방법인지는 모르지만)
그렇다면 임의로 주어진 두 정점을 통과해서 가는 경우는 무엇이 있을까, 또 어떤 경우들이 있을까 생각을 해보았다.
-
1 -> V1 -> V2 -> N -
1 -> V2 -> V1 -> N
이 두 가지 경우만 통과하면 된다. 나는 이 두가지 경우 말고도 아래의 경우를 생각하다가 시간을 많이 썼는데, 바보 같은 생각이었다.
예를 들면, V1과 V2가 연결되어 있지 않아 1- > V1 -> 1 -> V2 -> N 이런식으로 간다고 생각해보면, 다익스트라 알고리즘을 통해 만들어낸 그래프에서는 V1->V2 <= V1->1->V2 이기 때문에 생각할 필요가 없었다. 그냥 저 2가지 경우만 구해내면 된다.
그럼 저 2가지 경우는 어떻게 하면 될까?
-
정점 1, V1, V2에서의 다익스트라 그래프를 구한다.
-
1번 경우와 2번 경우가 가능한지 따진다. 둘다 가능하면, 최솟값을 답으로 입력하고, 하나만 가능하면 그 경우가 최솟값일 것이다.
이렇게 틀을 잡고 나면 나머지는 간단하다.
제출 코드
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
N,E = map(int, input().split())
graph = [[] for _ in range(N+1)]
distance = [[INF for _ in range(N+1)] for _ in range(N+1)]
for _ in range(E):
# a번 정점에서 b번 정점까지 양방향 길이 존재하고 그 거리가 c임.
a,b,c = map(int, input().split())
graph[a].append((b,c))
graph[b].append((a,c))
v1, v2 = map(int, input().split())
def dijkstra(start):
q = []
distance[start][start] = 0
heapq.heappush(q, (0,start))
while q:
dist, now = heapq.heappop(q) # 시작점에서 거리가 가장 짧은 정점과 그 거리를 받는 것.
if dist > distance[start][now]: # 그 거리가 테이블에 있는 거리보다 크면 따질 필요가 없다.
continue
for x in graph[now]: # x[0] : 도착점, x[1] : 현재 정점에서 x[0]까지의 거리 값.
cost = dist + x[1]
if cost < distance[start][x[0]]:
distance[start][x[0]] = cost
heapq.heappush(q, (cost,x[0]))
dijkstra(1)
dijkstra(v1)
dijkstra(v2)
# 경우를 따져준다.
answer = -1
flag1, flag2 = True, True
if distance[1][v1] == INF or distance[v1][v2] == INF or distance[v2][N] == INF:
flag1 = False
if distance[1][v2] == INF or distance[v2][v1] == INF or distance[v1][N] == INF:
flag2 = False
route1 = distance[1][v1] + distance[v1][v2] + distance[v2][N]
route2 = distance[1][v2] + distance[v2][v1] + distance[v1][N]
if flag1 == True and flag2 == True:
answer = min(route1, route2)
elif not flag1 and not flag2:
answer = -1
elif not flag1:
answer = route2
else:
answer = route1
if answer == INF:
answer = -1
print(answer)