[백준] 14938번 - 서강그라운드 (파이썬)

https://www.acmicpc.net/problem/14938

# 서강그라운드

import sys
input = sys.stdin.readline
N, m, r = map(int, input().split())
item = [0] + list(map(int, input().split()))
arr = [[sys.maxsize for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    arr[i][i] = 0
for _ in range(r):
    a, b, dist = map(int, input().split())
    arr[a][b] = dist
    arr[b][a] = dist

for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            if arr[i][j] > arr[i][k] + arr[k][j]:
                arr[i][j] = arr[i][k] + arr[k][j]

answer = 0
for i in range(1, N+1):
    can_get_item = [item[x] for x in range(1, N+1) if arr[i][x] <= m]
    answer = max(answer, sum(can_get_item))
print(answer)

 

플로이드와샬
1. 각 지역별 아이템을 items리스트에 입력을 받고, 인접 행렬을 정의한다.
2. 양방향임을 생각하면서 인접행렬을 초기화
3. 플로이드 와샬 알고리즘
    - i에서 j로 갈 때, k를 거쳐서 가는 경우가 더 짧을 경우 해당 값으로 업데이트
4. 인접 행렬의 각 행마다
    - can_get_item : 거리가 m이하인 노드들의 아이템 수를 가진 리스트
    - answer을 'can_get_item의 합'의 최댓값으로 초기화
5. answer 출력

 

문제

각 노드마다 특정 범위 내의 노드가 가진 아이템의 총개수를 구하는 문제

 

아이디어

최단거리 구하기 : 다익스트라, 플로이드와샬

아이템 개수의 최댓값을 구하기 위해 각 노드마다 체크를 해주어야 하므로

특정 노드에서 다른 노드들까지의 거리를 구하는 다익스트라 X

시간 복잡도를 만족하면 플로이드와 샬 O

 

시간 복잡도

N^3 (N=100) 만족