Jin의 일상

www.acmicpc.net/problem/14938

문제 설명

첫째 줄에는 지역의 개수(n), 수색 범위(m), 길의 개수(r)이 주어집니다.

둘째 줄에는 n개의 숫자가 차례대로 각 구역에 있는 아이템의 수를 나타냅니다.

세 번째 줄부터 r+2번째 줄 까지 지역의 번호 a, b와 길의 길이 i가 주어집니다.

이 때, 각 지역에서 수색 범위(m) 내에서 다른 지역으로 이동했을 때 얻을 수 있는 최대 아이템 개수를 구해야 합니다.

m이 5로 주어졌을 때 2번 지역에서는 "1번, 3번, 5번"으로 이동할 수 있습니다.

2번->1번->4번은 8(0+3+5)의 수색 범위를 가지므로 이동할 수 없습니다.

문제 특성

각 노드에서 다른 노드로 이동했을 때 최소 경로를 구해야 합니다.

따라서 다익스트라 알고리즘을 적용합니다.

알고리즘

1. 1 ~ n번 지역에서 다익스트라 알고리즘 수행  : 각 지역에서 다른 지역으로 이동했을 때 최소 경로를 구합니다.

3. 각 지역에서의 최소 경로 중 m 이하인 수색 범위의 구역에 있는 아이템 개수를 구합니다.

4. 이전 지역과 비교하여 더 많은 아이템 개수로 갱신합니다.

다익스트라 알고리즘

다익스트라 알고리즘의 전체 과정은 다음과 같습니다. 1번~4번 수행과정을 따라 알고리즘을 파악하시면 됩니다!

참고로 0번 인덱스의 [3, 5]에 대해 과정이 모두 수행된 다음에 [1, 3]에서 0(heap[1])과 더하고 dy와 비교하는 과정이 수행됩니다. 

이어서 각 리스트 변수에 대한 세부 사항을 설명하겠습니다.

1. graph는 각 노드 간의 정보를 담고 있습니다.

graph는 총 n 개의 길이를 가지며, 인덱스는 노드 번호를 의미합니다.

 - 문제에서 1번 지역을 graph에서는 0(1-1)번 인덱스로 담았습니다.

또한, graph의 각 인덱스는 복수 개의 [인접한 노드번호, 거리]를 가질 수 있습니다.

2. dy는  한 지역에서 다른 지역으로 이동할 때 최소 거리를 담고 있습니다.

 - dy는 총 n 개의 길이를 가지며, 인덱스는 노드 번호를 의미합니다.

 - dy의 인덱스 초기 값은 int의 최대 값으로 설정합니다. 이 값은 지역 간 이동할 수 있는 최소 거리를 의미합니다.

 - 가령, 2번 지역에서 4번 노드로 이동할 때는 8(3+5)이 최소거리입니다.  따라서 알고리즘이 수행된 후에 dy의 1번 인덱스는 8이 리턴되어야 합니다.

3. heap는  다른 지역으로 이동할 때, 중간 경로의 역할을 수행합니다.

- heap에 들어가는 초기 값은 (출발 지역 번호, 0)입니다. 뒤에 있는 0은 이동해야 하는 거리를 의미합니다.

  - 가령 3번 지역에서 출발한다면  (2, 0) 입니다. (출발 지역 번호-1이므로) 

  - 0번에서 0번을 이동하므로, 초기 거리는 0입니다.

- heap 리스트가 비었을 때 다익스트라 알고리즘은 종료됩니다.

코드

import sys
import heapq
sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def dijstra(x):
    dy = [sys.maxsize] * n
    dy[x] = 0
    heap = [[x, dy[x]]]
    while heap:
        node, dis = heapq.heappop(heap)
        for i in range(len(graph[node])):
            next = graph[node][i]
            if dy[next[0]] > dis + next[1]:
                dy[next[0]] = dis + next[1]
                heapq.heappush(heap, [next[0], dis + next[1]])
    return dy

if __name__ == "__main__":
    n, m, r = map(int, input().split())  # 지역의 개수, 수색범위, 길의 개수
    numItem = list(map(int, input().split()))  # 인덱스는 지역 번호를 의미
    graph = [[] for _ in range(n)]
    for _ in range(r):
        a, b, i = map(int, input().split())  # 연결된 지역의 번호(a, b), 길의 길이(i)
        graph[a - 1].append([b - 1, i])
        graph[b - 1].append([a - 1, i])
    res = 0
    for i in range(n):    # 각 노드에서 최소 경로탐색
        minPath = dijstra(i)
        add = 0
        for j in range(n):    # 최소 경로가 m 이하일 때 획득할 수 있는 아이템 수
            if minPath[j] <= m:
                add += numItem[j]
        res = max(res, add)
print(res)