[알고리즘][Python] 백준 14938 서강그라운드 문제 풀이

문제 출처 : www.acmicpc.net/problem/14938

14938번: 서강그라운드

---

문제 해석 : 일정한 거리를 탐색할 수 있다. 이때 가장 많은 아이템을 습득하기 위해서는 어디에 떨어져야 하는지는 구하는 문제이다.

 

문제 풀이 : 1. 워셜 플루이드 알고리즘을 통해서 모든 경로의 최소 거리를 구하여 계산 할 수 있다.

---

풀이 코드

INF = int(1e9)

N, M, R = map(int, input().split())
area_item = list(map(int, input().split()))
arr = [[INF] * N for _ in range(N)]

for _ in range(R):
    start, end, dist = map(int, input().split())
    arr[start-1][end-1] = min(arr[start-1][end-1], dist)
    arr[end-1][start-1] = min(arr[end-1][start-1], dist)

for k in range(N):
    for a in range(N):
        for b in range(N):
            arr[a][b] = min(arr[a][b], arr[a][k] + arr[k][b])
            if a == b:
                arr[a][b] = 0

max_value = 0

for i in range(N):
    temp_value = 0
    for j in range(N):
        if arr[i][j] <= M:
            temp_value += area_item[j]

    max_value = max(max_value, temp_value)

print(max_value)

---

 

가능한 다른 풀이 : 다익스트라 알고리즘을 이용해서 문제를 풀 수 있다.

 

---

풀이 코드

import heapq, sys
INF = sys.maxsize
input = sys.stdin.readline

def dijkstra(S):

    Q = []
    distance = [INF] * (N+1)

    heapq.heappush(Q, [0, S])
    distance[S] = 0

    while Q:
        now_dist, now_vertex = heapq.heappop(Q)

        for next_dist, next_vertex in arr[now_vertex]:
            if next_dist + now_dist < distance[next_vertex]:
                next_dist += now_dist
                distance[next_vertex] = next_dist
                heapq.heappush(Q, [next_dist, next_vertex])

    return distance

N, M, R = map(int, input().split())

area_item = list(map(int, input().split()))
area_item.insert(0, 0)

arr = [ [] for _ in range(N+1)]

for _ in range(R):
    start, end, dist = map(int, input().split())

    arr[start].append([dist, end])
    arr[end].append([dist, start])

max_value = int(-1e9)

for i in range(1, N+1):
    temp_sum = 0
    result = dijkstra(i)

    for j in range(1,N+1):
        if result[j] <= M:
            temp_sum += area_item[j]

    max_value = max(max_value, temp_sum)

print(max_value)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.