문제

문제 이해

이 문제는 다익스트라인데 조금 활용이 필요하다. 어려운 건 아니라서 그냥 생각만 조금 하면 풀 수 있다.

1번 노드부터 N번 노드까지 돌아가면서 다익스트라를 돌리고, distance값이 수색범위 안일 경우에 item_number에 있는 인덱스에 맞는 값을 더해주면 된다.

코드

# 백준 14938번 서강그라운드

# 읽는 속도 효율화
import sys
input = sys.stdin.readline

# Import PriorityQueue
from queue import PriorityQueue

# Function Dijkstra Algorithm
def Dijkstra(cur_distance, start_node):
    global result, distance

    pq = PriorityQueue()
    pq.put([cur_distance, start_node])
    distance[start_node] = 0 # 첫 노드 거리 0

    while not pq.empty():

        cur_distance, cur_node = pq.get()
        
        # 어차피 갱신되지 않은 값은 넘겨준다
        if cur_distance > distance[cur_node]:
            continue 

        for adj_node, adj_distance in adj_list[cur_node]:

            temp_distance = cur_distance + adj_distance

            if temp_distance < distance[adj_node]:
                distance[adj_node] = temp_distance
                pq.put([temp_distance, adj_node])

    return
    
# 0. 입력 및 초기화
# N 노드 갯수, M 수색범위, R 간선 갯수
N, M, R = map(int, input().split())
INF = int(1e12)

item_number = list(map(int, input().split()))

# 1. Create adj_list
adj_list = [[] for _ in range(N+1)]
for _ in range(R):
    a, b, t = map(int, input().split())
    adj_list[a].append([b, t])
    adj_list[b].append([a, t])

# 2. Excute Dijkstra Algorithm & Print result
result = 0
for i in range(1, N+1):
    distance = [INF] * (N+1)
    Dijkstra(0, i)
    sum = 0

    for j in range(1, N+1):
        if distance[j] <= M:
            sum += item_number[j-1]
    
    result = max(result, sum)

print(result)

여담이지만, 드디어 실버 1에 도달했다. 처음에 DFS를 배우면서 알고리즘 공부를 시작할때는 학교가기전까지 골드찍는게 목표였는데 생각보다 널널하게 도달할 수 있을 것 같다. 요즘에 좀 아파서 집중하지 못했는데 힘내야 겠다.