[백준 13141번] Ignition (Python3)

import sys
input = sys.stdin.readline

N,M = map(int,input().split())

DP = [[1e9]*N for i in range(N)]
graph = []
for _ in range(M):
  a,b,c = map(int,input().split())
  DP[a-1][b-1] = DP[b-1][a-1] = min(DP[a-1][b-1],c)
  graph.append((a-1,b-1,c))

for k in range(N):
  for i in range(N):
    for j in range(N):
      DP[i][j] = min(DP[i][j],DP[i][k]+DP[k][j])
for i in range(N):
  DP[i][i] = 0
result = 1e9
for i in range(N):
  MAX = 0
  for a,b,c in graph:
    MAX = max(MAX,(DP[i][a]+c+DP[b][i])/2)
  result = min(result,MAX)
print(result)

플로이드 워셜로 해결하였다.

 

기본적인 풀이를 설명하면,

1. 플로이드 워셜 알고리즘으로 각 노드간 최소거리를 측정

2. 모든 노드마다 모든 간선에 대해서 간선을 지우는데 걸리는 시간을 측정하고 ((플로이드 워셜로 측정한 노드간 길이 + 간선의 길이)/2) 각 노드의 간선을 지우는데 걸리는 시간의 최댓값의 최솟값이 곧 결과이다.

 

실수할 여지가 좀 있는 문제였는데, 일단 자기자신으로 가는 거리를 0으로 초기화시켜주어야 한다. 왜냐하면 자기자신을 지나는 간선을 태우는데 걸리는 시간이 잘못 측정될 수 있기 때문이다. 또, 인접행렬을 만들 때, 같은 노드간에 여러개의 간선이 입력될 수 있기 때문이다.

 

예제에 위의 예시에 해당하는 경우가 있어서 한결 편하게 풀 수 있었다.

 

 

오늘의 교훈) 인접행렬을 만들때, 항상 여러개의 간선에 조심하자