[BOJ/Python] 14938번 문제풀이

문제 설명

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.

각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 4라고 하자. ( 원 밖의 숫자는 지역 번호, 안의 숫자는 아이템 수, 선 위의 숫자는 거리를 의미한다) 예은이가 2번 지역에 떨어지게 되면 1번,2번(자기 지역), 3번, 5번 지역에 도달할 수 있다. (4번 지역의 경우 가는 거리가 3 + 5 = 8 > 4(수색범위) 이므로 4번 지역의 아이템을 얻을 수 없다.) 이렇게 되면 예은이는 23개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.

입력

첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.
둘째 줄에는 n개의 숫자가 차례대로 각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.
세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.
지역의 번호는 1이상 n이하의 정수이다. 두 지역의 번호가 같은 경우는 없다.

출력

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

---

풀이 과정

우선 이 문제는 크게 두가지 방법이 있다. 바로 플로이드 워셜 혹은 다익스트라 알고리즘을 사용하여 해결할 수 있다. 물론 아직 다익스트라 알고리즘을 완벽히 이해하고 사용할 수 있는 단계는 아니지만 플로이드 워셜 알고리즘을 처음 알게되어 해당 알고리즘을 알아보고자 플로이드-워셜 알고리즘 방식으로 문제를 풀어보았다.

 

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우 사용하는 알고리즘으로, 소스코드가 다익스트라에 비해 매우 짧아 구현이 쉽다는 특징을 가지고 있다. 또한 플로이드 워셜 알고리즘도 다익스트라와 유사하게 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만, 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다.

출처 : https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm

해결 과정

플로이드-워셜 알고리즘을 사용하면 입력을 받고 거리 리스트를 초기화 시켜준 이후 삼중 for문을 돌면서 최단 거리를 갱신하는 과정으로 문제를 풀 수 있다.

import sys
input = sys.stdin.readline
INF = int(1e9)

n,m,r = map(int,input().split())  # n: 노드의 개수, m: 간선의 최대 길이, r: 길의 개수

items = [-1] + list(map(int,input().split()))  # 각 노드에 아이템의 가치를 나타내는 리스트

distance = [[INF for i in range(n + 1)] for j in range(n + 1)]  # distance[i][j]: 노드 i에서 노드 j까지의 최단 거리

# 각 노드에서 자기 자신으로 가는 거리는 0으로 초기화
for i in range(1,n+1):
    distance[i][i] = 0

# 간선 정보를 입력받아 distance 행렬 업데이트
for i in range(r):
    a,b,l = map(int,input().split())
    distance[a][b] = l
    distance[b][a] = l

# Floyd-Warshall 알고리즘을 이용하여 최단 거리 갱신
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            if distance[j][k] > distance[j][i] + distance[i][k]:
                distance[j][k] = distance[j][i] + distance[i][k]

result = 0

# 각 노드에서 아이템을 수집하며 얻을 수 있는 가치 계산
for i in range(1,n + 1):
    temp = 0
    for j in range(1, n + 1):
        if distance[i][j] <= m:
            temp += items[j]
    if temp > result:
        result = temp

print(result)  # 결과 출력