[최단 경로] 최단 경로 알고리즘 (4) 실전 문제 - 미래 도시

이코테 p.259 실전 문제 - 미래 도시

입력 예시 1

5 7 1 2 1 3 1 4 2 4 3 4 3 5 4 5 4 5

출력 예시 1

3

입력 예시 2

4 2 1 3 2 4 3 4

출력 예시 2

-1

내 소스코드 ver. 다익스트라

• 1번 노드에 대해 다익스트라 알고리즘을 적용한 후, 1번 노드부터 k번 노드까지의 거리 구하기
• k번 노드에 대해 다익스트라 알고리즘을 적용한 후, k번 노드부터 x번 노드까지의 거리 구하기
• 연결된 2개의 회사는 양방향으로 이동할 수 있다고 하였으니 특정 간선 정보에 대해 D[a][b]와 D[b][a] 둘 다 설정해줘야 함

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# 입력받기
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append((b, 1))
x, k = map(int, input().split())

# 최단 거리 정보를 저장할 거리 테이블 초기화
distance = [INF] * (n + 1)

# 다익스트라 알고리즘
def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0
  while q:
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
      continue
    for i in graph[now]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))

result = 0
# 시작 노드가 1일 때 다익스트라 알고리즘 수행
dijkstra(1)
# 1번 노드부터 k번 노드까지의 최단 경로 더하기
result += distance[k]
# 시작 노드가 k일 때 다익스트라 알고리즘 수행
dijkstra(k)
# k번 노드부터 x번 노드까지의 최단 경로 더하기
result += distance[x]

if result >= INF:
  print(-1)
else:
  print(result)

내 소스코드 ver. 플로이드 워셜

• 모든 노드로부터 모든 노드까지 가는 최소 이동 시간을 플로이드 워셜 알고리즘으로 구함

import sys
input = sys.stdin.readline
INF = int(1e9)

# n, m 입력받기
n, m = map(int, input().split())

# 최단 거리 정보를 저장할 거리 테이블 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(1, n + 1):
  for b in range(1, n + 1):
    if a == b:
      graph[a][b] = 0

for _ in range(m):
  a, b = map(int, input().split())
  graph[a][b] = 1
  graph[b][a] = 1

# x, k 입력 받기
x, k = map(int, input().split())

# 플로이드 워셜 알고리즘
for c in range(1, n + 1):
  for a in range(1, n + 1):
    for b in range(1, n + 1):
      graph[a][b] = min(graph[a][b], graph[a][c] + graph[c][b])

# 1번 노드에서 K번 노드를 거쳐 X번 노드까지의 최소 이동 시간
result = graph[1][k] + graph[k][x]
if result >= INF:
  print(-1)
else:
  print(result)

 

• 교재에서는 플로이드 워셜 알고리즘을 적용하여 위와 같이 해결함
  • N의 범위가 100 이하로 작기 때문에 플로이드 워셜 알고리즘을 이용해도 빠르게 풀 수 있음