지역의 개수 n, 수색범위 m, 길의 개수 r에 대해서
각 지역마다 주어진 아이템 수와
지역을 연결하는 길의 길이가 주어질때,
얻을 수 있는 최대 아이템 개수를 구하는 문제
문제
예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.
각 지역은 일정한 길이 l

주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 4라고 하자.
입력
첫째 줄에는 지역의 개수 n
둘째 줄에는 n개의 숫자가 차례대로 각 구역에 있는 아이템의 수 t
세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l
지역의 번호는 1이상 n이하의 정수이다. 두 지역의 번호가 같은 경우는 없다.
출력
예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.
# 다익스트라
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
n, m, r = map(int, input().split())
items = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(r):
a, b, l = map(int, input().split())
graph[a].append((b, l))
graph[b].append((a, l))
def dijkstra(s):
# 낙하지점 s에서 다른 지역까지의 최단 거리를 구하는 함수
dist = [16]*(n+1)
q = [(0, s)]
dist[s] = 0
while q:
d0, n0 = heappop(q)
if dist[n0] < d0:
continue
for n1, d1 in graph[n0]:
if (d:=d0+d1) < dist[n1]:
dist[n1] = d
heappush(q, (d, n1))
# 수색 범위 m 내의 지역의 아이템 수를 합산해서 반환
tmp = 0
for i, d in enumerate(dist[1:], 1):
if d <= m:
tmp += items[i]
return tmp
ans = 0
for i in range(1, n+1):
# 모든 지역에 대해서 최대 아이템 수 구하기
if ans < (tmp:=dijkstra(i)):
ans = tmp
print(ans)
# 플로이드-워셜
import sys
input = sys.stdin.readline
INF = float('inf')
n, m, r = map(int, input().split())
items = [0] + list(map(int, input().split()))
graph = [[INF]*(n+1) for _ in range(n+1)]
for _ in range(r):
a, b, l = map(int, input().split())
graph[a][b] = l
graph[b][a] = l
# 모든 지점간 최단 거리 구하는 함수
for node in range(1, n+1):
graph[node][node] = 0
for i in range(1, n+1):
for j in range(i+1, n+1):
if graph[i][j] > graph[i][node] + graph[node][j]:
graph[i][j] = graph[i][node] + graph[node][j]
graph[j][i] = graph[i][j]
ans = 0
for i in range(1, n+1):
# i 지점에서 낙하했을 때, 최대 아이템 수를 구함
tmp = 0
for j in range(1, n+1):
if graph[i][j] <= m:
tmp += items[j]
# 모든 낙하지점 중에서 최대 아이템 수를 구함
if ans < tmp:
ans = tmp
print(ans)
예제 입력 1
5 5 4
5 7 8 2 3
1 4 5
5 2 4
3 2 3
1 2 3
예제 출력 1
23
'IT > Python' 카테고리의 다른 글
[백준] 14502번 연구소 [Python] 1 | 2023.12.28 |
---|---|
[백준] 12851번 숨바꼭질 2 [Python] 1 | 2023.12.27 |
[백준] 9935번 문자열 폭발 [Python] 1 | 2023.12.26 |
[백준] 1987번 알파벳 [Python] 0 | 2023.12.25 |