1 minute read

문제

접근 방법

모든 집하장에서 다른 모든 집하장까지의 최단 거리에 대한 문제이기 때문에 우선 플로이드 워셜을 떠올렸다. N=200이어서 시간 제한을 충족할 수 있다.

하지만 이 문제는 일반적인 문제와 다르게 최단 거리의 경로에 대한 문제였다. 한 지점에서 다른 지점으로 최단 거리로 가기 위해서 거쳐야 하는 중간 지점을 어떻게 판단해야 할까를 생각해냈어야 했다. 생각해낸 것은 시작 지점에서 중간 지점까지의 최단 거리 + 중간 지점에서 끝점까지의 최단 거리 = 시작 지점에서 끝점까지의 최단 거리를 만족한다면 그 중간 지점은 최단 경로의 일부분이지 않을까 였다.

그래서 우선 플로이드 워셜로 모든 지점 간 최단 거리를 구하였다.

그리고 시작점과 연결된 지점 중에 최단 경로를 구성하는 지점을 구해야 하기 때문에 distances[시작점][끝점] == 시작점과 직접 연결된 지점(m)까지의 거리 + distances[m][끝점]을 만족하는 지점들을 구했다. 이때 distances[시작점][끝점] == distances[시작점][m] + distances[m][끝점]으로 조건문을 하지 않는 이유는 이렇게 하면 시작점에서 m으로 최단 거리로 가기 위해서 다른 지점을 거쳐서 갈 수 있는 경우가 포함되기 때문이다. 즉, 이렇게 하면 시작점에서 끝점으로 가기 위해 제일 먼저 거쳐가는 지점(m)을 구하지 못하게 될 수도 있게 된다.

정답 코드

import sys
import heapq
from collections import deque
input = sys.stdin.readline

"""
floyd warshall로 모든 점에서 다른 지점들까지의 최단 거리를 구함

이 거리를 바탕으로 경로를 파악해야함. 가장 먼저 방문하는 노드를 구해야 하기 때문에 시작점과 연결된 노드들 중에 최단 경로를 구성하는 노드를 알아내야 함

distances[start][end] = distances[start][mid] + distances[mid][end]를 만족하는지 보아야 한다.
"""

n,m = map(int, input().split())

table = [[0]*(n+1) for _ in range(n+1)]

graph = [[] for _ in range(n+1)]
distances = [[int(1e9)]*(n+1) for _ in range(n+1)]

for i in range(n+1):
  distances[i][i] = 0
  
for _ in range(m):
  a,b,c = map(int, input().split())
  graph[a].append((b,c))
  graph[b].append((a,c))
  distances[a][b] = c
  distances[b][a] = c

def floyd():
  for mid in range(1,n+1):
    for start in range(1,n+1):
      for end in range(1,n+1):
        new_dist = distances[start][mid] + distances[mid][end]
        if new_dist < distances[start][end]:
          distances[start][end] = new_dist


floyd()

for i in range(1,n+1):
  for j in range(1,n+1):
    if distances[i][j] == int(1e9):
      distances[i][j] = 0
      
for s in range(1,n+1):
  for e in range(1,n+1):
    for m,w in graph[s]:
      #최단 경로를 구성하는 지점인지 확인하는 조건문
      if distances[s][e] == distances[m][e] + w:
        table[s][e] = m
      
for i in range(1,n+1):
  for j in range(1,n+1):
    if table[i][j] == 0:
      print('-', end=' ')
    else:
      print(table[i][j], end=' ')
  print()

You May Also Enjoy