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

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

14938번: 서강그라운드

문제





그래프가 주어지고 수색범위 내부에서 수색했을 때 가장 아이템을 많이 주울 수 있는 경우의 수를 구하는 문제이다.

---

풀이

그래프간의 최단경로를 구하는 문제이므로 다익스트라 알고리즘을 사용하였다.

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

기본적인 구현은 위와같다.

우선순위 큐를 사용하여 구현하였고 해당 알고리즘을 사용하여 현재 위치부터의 최단경로를 구할 수 있었다.

 

이 문제에서의 특정한 점은 수색범위 m을 넘어가면 수색이 불가능하다는 점인데

이는 다익스트라 알고리즘을 거친 후 거리값에서 m값을 넘어가는 노드는 제외하고 합하면 해결된다.

 

for i in range(1, n + 1):
    distance = [sys.maxsize] * (n + 1)
    dijkstra(i)
    tmp = 0
    for d in range(1, n + 1):
        if m >= distance[d]:
            tmp += items[d]
            
    result = max(result, tmp)

위와같이 모든 노드에 대해서 다익스트라 알고리즘을 적용시켜준 후 m값을 넘어가지 않는 경로를 모두 더해준다.

최종적으로 이미 존재하는 값과 비교하여 result를 갱신 후 출력한다.

 

코드

import heapq
import sys

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

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

graph = [[] for i in range(n + 1)]

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

result = 0

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
        

for i in range(1, n + 1):
    distance = [sys.maxsize] * (n + 1)
    dijkstra(i)
    tmp = 0
    for d in range(1, n + 1):
        if m >= distance[d]:
            tmp += items[d]
            
    result = max(result, tmp)
print(result)