[BOJ/백준] 14938 서강그라운드 파이썬

문제 링크 : https://www.acmicpc.net/problem/14938

14938번: 서강그라운드

 

각 노드에서 출발하여 정해진 가중치 이내로 갈 수 있는 노드들이 가지고 있는 값의 합의 최대값을 구하는 문제이다.

모든 노드에서 각 노드로 최단거리를 구해서 그 길이가 m 이하인 것들의 아이템수의 합을 구하고 그중 최대값을 구하면 된다.

 

모든 노드에 대해서 최단거리는 플로이드와샬과 다익스트라로 해결할 수 있다.

해당 문제는 노드의 개수가 최대 100개 이므로 플로이드와샬로 해결 가능하다.

 

플로이드 와샬을 모든 노드 사이의 최단 거리를 계산하는 것으로 다이렉트로 가는 경로, 거쳐가는 경로중 더 작은 값으로 갱신해가는 알고리즘이다.

자세한 내용은 나동빈 씨의 강의를 참고하자.

링크 : https://www.youtube.com/watch?v=hw-SvAR3Zqg 

 

또는 모든 노드에서 다익스트라를 돌려서 해결할 수 있다.

시작점에서 갈 수 있는 모든 노드의 최단거리를 구하고 이를 모든 노드에서 수행하면 된다.

 

두 알고리즘으로 각 노드에서 출발하여 도달할 수 있는 노드 중 거리가 m 이하인 곳의 아이템의 개수를 합해서 답을 구하면 된다. 한가지 주의할 점이라면 시작점과 시작점 사이의 거리는 0이라는 점이다.

 

 

플로이드 와샬 방식

from sys import stdin

input = stdin.readline
INF = 9876543210

n,m,r = map(int, input().split())
items = [0]+list(map(int, input().split()))

adj_mat = [[INF]*(n+1) for _ in range(n+1)]
for _ in range(r):
    a,b,l = map(int, input().split())
    adj_mat[a][b] = adj_mat[b][a] = l

def solv():
    global adj_mat
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                if i == j:
                    adj_mat[i][j] = 0
                elif adj_mat[i][j] > adj_mat[i][k] + adj_mat[k][j]:
                    adj_mat[i][j] = adj_mat[i][k] + adj_mat[k][j]

    answer = 0
    for dist in adj_mat:
        total = 0
        for idx in range(1,n+1):
            if dist[idx] <= m:
                total += items[idx]
        answer = max(answer,total)
    print(answer)

solv()

 

다익스트라 방식

주의할 점이라면

최단거리를 저장할때 현재 점을 기준으로 저장하는게 아니라 시작점을 기준으로 저장해야한다.

from sys import stdin
from heapq import heappush, heappop
input = stdin.readline
INF = 9876543210

n,m,r = map(int, input().split())
items = [0]+list(map(int, input().split()))

adj_list = [[] for _ in range(n+1)]
dist = [[INF]*(n+1) for _ in range(n+1)]

for _ in range(r):
    a,b,l = map(int, input().split())
    adj_list[a].append((b,l))
    adj_list[b].append((a,l))

def solv():
    for start in range(1,n+1):
        dijkstra(start)

    answer = 0
    for row in dist:
        total = 0
        for idx in range(1,n+1):
            if row[idx] <= m:
                total += items[idx]
        answer = max(answer,total)
    print(answer)
def dijkstra(start):
    global dist
    pq = [(0,start)]
    dist[start][start] = 0
    while pq:
        now_cost,now = heappop(pq)

        for nxt,nxt_cost in adj_list[now]:
            if dist[start][nxt] > now_cost+nxt_cost:
                dist[start][nxt] = now_cost + nxt_cost
                heappush(pq,(dist[start][nxt],nxt))
solv()