[BOJ] 14938번 서강그라운드 / 사용언어 : 파이썬(python)

※ 문제링크

14938번: 서강그라운드

해당 문제는 양의 가중치가 있는 최단경로를 구하는 문제로 다익스트라 알고리즘을 활용하여 해결할 수 있는 문제였다. 기본적인 다익스트라 알고리즘을 작성하여 각각의 정점에서 다른 정점으로 가는 최단 경로를 확인한 후 조건에 맞으면 item의 개수를 더해서 얻을 수 있는 가장 많은 item수를 출력하면 되는 문제였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들 각각의 변수들에 저장하고, 각 정점에 대한 item의 개수는 리스트에 저장한다.

2. 정점의 개수에 +1한 수만큼 리스트를 작성하고, 반복문을 활용하여 그래프로 구현해준다(양방향임을 주의)

3. 각 정점에서 다른 정점으로 갈 때의 최단경로를 확인할 다익스트라 함수를 작성한다.

4. 2중 반복문을 활용하여 모든 정점에서의 얻을 수 있는 최대 item의 개수를 구하고, max함수를 이용해 결과를 출력한다.

+ 시간 및 메모리 절감을 위해 입력값은 sys를 이용하였습니다.

 

from heapq import heappush, heappop
import sys

# input = sys.stdin.readline
n, m, r = map(int, input().split()) # n: 지역의 개수 / m: 수색범위 / r: 길의 개수
items = [0] + list(map(int, input().split()))
graph = [[[0, i]] for i in range(n+1)]
for _ in range(r):
    s, e, w = map(int, input().split())
    graph[s].append([w, e])
    graph[e].append([w, s])

def dijkstra(start, number, graph):
    heap = []
    dp = [float('inf') for _ in range(number+1)]
    heappush(heap, [0, start])

    while heap:
        wei, n = heappop(heap)
        if dp[n] < wei:
            continue
        for wei_n, n_n in graph[n]:
            wei_nch = wei + wei_n
            if wei_nch < dp[n_n]:
                dp[n_n] = wei_nch
                heappush(heap, [wei_nch, n_n])
    
    return dp

values = [0]
for i in range(1, n+1):
    value = items[i]
    cp = dijkstra(i, n, graph)
    for k in range(1, n+1):
        if i == k:
            continue
        if cp[k] <= m:
            value += items[k]
    values.append(value)
print(max(values))

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.