[백준14938&파이썬] 플로이드와샬을 활용해 모든 정점에서 시작하여 모든정점까지 도착하는 경우를 구하자

# 문제

백준 14938 서강그라운드 파이썬 풀이

14938번: 서강그라운드

# 코드

'''
  - 한 정점에서 모든정점까지의 최단거리를 구하자. ( X )
    - 다익스트라 알고리즘 ?? 
  - 아니다 문제를 잘못 봤다. 
    - 플로이드 와샬로 모든정점에서 모든정점까지의 최단거리를 구해야 한다.
'''
import sys

def print2D(arr) :
  for i in arr :
    print(*i)

# n : 지역의 개수
# m : 수색범위
# r : 길의 개수
n, m, r = map(int, sys.stdin.readline().split())
items = list(map(int, sys.stdin.readline().split()))
graph = [[float('inf')] * (n+1) for _ in range(n+1)]

for _ in range(r):
  a, b, c = map(int, sys.stdin.readline().split())
  graph[a][b] = min(graph[a][b], c)
  graph[b][a] = min(graph[b][a], c)

# 대각행렬(자기 자신)은 0으로 초기화 한다.
for i in range(n+1) :
  graph[i][i] = 0


# 플로이드 와샬
for pivot in range(1,n+1) :
  for start in range(1,n+1) :
    for end in range(1,n+1) :
      cost = graph[start][pivot] + graph[pivot][end] # 피벗을 거쳐가는 것과 비교하기 위해서
      if cost < graph[start][end] :
        graph[start][end] = cost

# print2D(graph)

result = 0
for start in range(1,n+1) :
  sum = 0
  for end in range(1,n+1) :
    if graph[start][end] <= m : # 수색범위 이내이면
     sum  += items[end-1] # 범위 맞춰줘야함
  result = max(result,sum)

print(result)

# 풀이

• 문제를 해결하기 위해서는 모든정점에서 시작하여 모든정점까지 가는 거리의 최단경로를 구해야 한다.
• 거리의 최단경로를 구했다면, 이동가능 거리(m)이내로 이동 가능한 정점들에 대하여, item의 합들을 구한다.
• 플로이드 와샬은 n^3의 시간복잡도를 가진다. 그렇기 때문에 노드(정점)의 개수가 적을 경우 유용하다. 
• 이 문제의 경우 제시된 정점(지역)의 개수가 (1 <= n <= 100) 이기 때문에 100*100*100 해봐야 1,000,000으로 백만밖에 되지 않는다.
• 다익스트라, 크루스칼, 플로이드와샬 알고리즘을 오랜만에 접하니 다 까먹었다. 다시 한번 훓어 봐야 겠다.