백준 14938 : 서강그라운드 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline

def Dijkstra(start):

    dp[start]=0
    heap=[] ; heapq.heappush(heap,(0,start))

    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

        for next_value,next_node in graph[node]:

            next_value+=value

            if next_value<dp[next_node]:
                dp[next_node]=next_value

                heapq.heappush(heap,(next_value,next_node))
INF=int(1e9)

N,M,R=map(int,input().split()) # 지역개수 , 수색범위 , 길의 개수
Item=list(map(int,input().split())) # 지역번호마다의 아이템수

graph=[ [] for _ in range(N+1) ] ; Answer=0


for i in range(R):

    a,b,l=map(int,input().split())
    graph[a].append((l,b))
    graph[b].append((l,a)) #양방향 , 가중치먼저 넣어줌.

for i in range(1,N+1):
    dp = [INF] * (N + 1)

    Dijkstra(i)
    total = 0
    for j in range(1,len(dp)):

        if dp[j]<=M: # 수색가능한 범위라면
            total+=Item[j-1]


    if Answer<total:
        Answer=total

print(Answer)

📌 어떻게 접근할 것인가?

문제에서 주어진 것은 임의의 노드에 떨어졌을때 수색가능한 범위중 가질수 있는 아이템의 최대 개수를 구하는 것이다.

따라서 시작 노드를 정하고 다른 노드로 가는 최단 경로를 구해준다.
이때 다른노드로 가는 최단경로가 수색범위 내에 있을때 , 아이템을 얻을 수 있다.

그리고 문제에서는 시작노드를 정해주었지 않았으므로 모든 시작노드에 대해서 탐색을 해야한다.

따라서 최단경로를 구하기 위해 다익스트라 알고리즘을 사용했으며 모든 시작노드에서 다익스트라를 통해 다른 모든 노드에 대한 최단경로를 구한 후 탐색범위보다 값이 작거나 같으면 아이템을 얻는다.

따라서 시작노드에 대한 모든 탐색가능한 아이템의 총 합을 구해주고 그중의 최대값을 출력한다.