[백준] 14938번 : 서강 그라운드

14938번: 서강그라운드

14938번: 서강그라운드

🤔 문제분석

플로이드 워셜, 데이크스트라를 떠올리면 된다.

플로이드워셜

플로이드 워셜로 모든 노드까지의 모든 최단경로를 구한뒤, i번노드에서 다른노드까지 거리가 m이하인 경우만 아이템을 획득하게 만들면 된다.

데이크스트라

i번 노드에서 다른노드까지의 최단 거리를 구한뒤 ( 데이크스트라 ) 모든 거리가 m 이하인 경우만 아이템을 획득 할 수 있으므로 m이하인 거리만 item을 획득하게 하면된다.

💻 코드

플로이드워셜

import sys
input = sys.stdin.readline

n, m, r = map(int, input().split())

items = list(map(int, input().split()))
INF = sys.maxsize
distance = [[INF for _ in range(n+1)] for _ in range(n+1)]

for i in range(1, n+1):
    distance[i][i] = 0

for _ in range(r):
    a, b, l = map(int, input().split())
    distance[a][b] = l
    distance[b][a] = l
    
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i != j:
                distance[i][j] = min(distance[i][k] + distance[k][j], distance[i][j])

ans = 0
for i in range(1, n+1):
    count = items[i-1]
    for j in range(1, n+1):
        if i != j:
            if m >= distance[i][j]:
                count += items[j-1]
    ans = max(count, ans)
    
print(ans)

데이크스트라

import sys
import heapq

input = sys.stdin.readline

n, m, r = map(int, input().split())

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

edge = [[] for _ in range(n+1)]
for _ in range(r):
    a, b, l = map(int, input().split())
    edge[a].append((b, l))
    edge[b].append((a, l))
    
def dijikstra(start):
    queue = []
    INF = sys.maxsize
    distance = [INF for _ in range(n+1)]
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    score = items[start-1]
    while queue:
        cost, node = heapq.heappop(queue)

        if cost > distance[node]:
            continue
        
        if m >= cost and distance[node] > cost:
            score += items[node-1]
        
        distance[node] = cost
        
        for child, c in edge[node]:
            newcost = cost + c
            if distance[child] > newcost:
                heapq.heappush(queue, (newcost, child))
    
    return score

ans = 0
for i in range(1, n+1):
    ans = max(ans, dijikstra(i))
    
print(ans)

🎯 피드백 및 개선사항

이번문제는 비교적 쉽게 풀었습니다. 플로이드 워셜 알고리즘과 데이크스트라 알고리즘을 알고 있다면 문제를 딱 읽자마자 해당 풀이법이 생각 날 것 입니다.