[BOJ] 백준 14938번 서강그라운드 | python 파이썬 코드, 해설, 풀이

백준 14938번 서강그라운드 문제 파이썬 풀이입니다.

14938번: 서강그라운드 (acmicpc.net)

14938번: 서강그라운드

2017 SPC에 출제 되었던 문제입니다. 한 노드에서 각 노드까지의 최단거리를 알아야하기에, 최단 경로 탐색 알고리즘인 다익스트라(Dijkstra) 알고리즘으로 풀 수 있는 문제입니다. 다익스트라 알고리즘은 N*logN 시간복잡도를 가지게 되는데, 총 N개의 노드를 시작점으로 탐색해야기에 N개 * N*logN 의 시간복잡도를 필요로 하고, N은 최대 100이기에 1초내에 충분히 돌릴 수 있습니다.

 

from collections import deque
import sys
INF = sys.maxsize
 
n, m, r = map(int, input().split())
score = [0] + list(map(int, input().split()))
v = [[] for _ in range(n+1)]
for _ in range(r):
    a, b, l = map(int, input().split())
    v[a].append([b, l])
    v[b].append([a, l])
 
maximum = 0
for start_node in range(1, n+1):
    queue = deque()
    queue.append([start_node, 0])
    distance = [INF] * (n+1)
    distance[start_node] = 0
    while (queue):
        now_node, now_cost = queue.popleft()
        for new_node, new_cost in v[now_node]:
            if (distance[new_node] > new_cost + now_cost):
                distance[new_node] = new_cost + now_cost
                queue.append([new_node, new_cost + now_cost])
    temp_score = 0
    for i in range(1, len(distance)):
        if (distance[i] <= m):
            temp_score += score[i]
    maximum = max(maximum, temp_score)
print(maximum)
 

14번 line부터 각 노드를 시작점으로 설정하게 되며, 무한대로 초기화 시킨 distance 배열에 최단 거리를 저장하며 갱신하게 됩니다.

19번 line부터 현재의 node를 queue에서 pop하여 주변의 노드(갈 수 있는 노드)와 distance에 저장된 거리를 비교하며 순회하게 됩니다.

26번 line부터 최종적으로 결정된 최단거리를 m과 비교하여 갈 수 있는 곳인지 확인한 후 score를 계산해 maximum을 갱신시켜 주게 됩니다.