[백준][Python] 14938번 서강그라운드 - 코팩

풀이

플로이드워셜, BFS, 다익스트라 전부가 가능한 문제.

- BFS: 예은이의 수색범위를 생각하면서 노드를 방문해야한다. 두 점을 거쳐 지나갈 경우, 합산 필요.

- 다익스트라: 한 노드에서 모든 노드까지의 최단거리를 계산하는 알고리즘이기에 for문을 통해서 모든 노드를 다익스트라 알고리즘에 넣어서 돌려야함.

- 플로이드워셜: 모든 노드에서 모든 노드까지의 거리를 한번에 구해주는 알고리즘.

 

저는 플로이드워셜로 문제를 풀어주었습니다. 

https://sunghyun98.tistory.com/66

[알고리즘] 플로이드 워셜

 

코드

# 14938번 서강그라운드
import sys
INF = sys.maxsize
n, m, r = map(int, input().split())
item = list(map(int, input().split()))
graph = [[INF] * (n) for i in range(n)]
for _ in range(r):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

for i in range(n):
    for j in range(n):
        if i == j:
            graph[i][j] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

# 여기까지는 플로이드워셜 기존 알고리즘과 동일.

ans = 0
for i in range(n):
    total = 0
    for j in range(n):
    # 한 노드에서 모든 노드로의 최단거리가 수색범위를 넘지않아야함.
        if graph[i][j] <= m:
            total += item[j]
    ans = max(total, ans)

print(ans)

출력결과