[백준] 서강그라운드

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

14938번: 서강그라운드

플로이드 워셜(Floyd-Warshall) 알고리즘을 사용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면,

예은이가 특정한 지역에 내려서 거리 m이하로 도착할 수 있는 곳에서 아이템을 먹을 때, 먹을 수 있는 아이템의 최대 갯수를 return해야 합니다.

실제로 문제를 한번 읽어보는 것이 좋습니다.

 

<Solution>

우선 도시가 만약 1~5까지 있다고 생각해 봅시다. 이 때, 예은이가 먹을 수 있는 아이템을 각 도시별로 모두 구해서 그중에서 최댓값을 구해야 하는 것을 알 수 있습니다. 

 

이 때 조금만 생각해보면 1,2,3,4,5 모두에 대해 다른 도시들 까지의 거리정보를 사용 해야 한다는 것을 알 수 있습니다. 다익스트라의 경우 출발지가 고정 되어 있는 경우에 유리합니다. 하지만 현재는 모든 출발지에서 모든 도착지로의 최단 거리를 구해야 하기에, 플로이드 워셜 알고리즘을 사용해야 할 것을 추측할 수 있습니다.

 

플로이드 워셜 알고리즘은 O(n^3)의 시간복잡도를 가지기에 문제 상황이 이 알고리즘에 reasonable한지 check해보면, 

지역의 갯수가 100개 이하로 100^3 = 1,000,000 으로 시도해 볼 만합니다. 

 

따라서 

1. 플로이드 워셜 알고리즘으로 모든 도시들 간의 거리를 구한다. 2. 예은이의 이동 거리(m)을 통해 먹을 수 있는 아이템 수를 도시별로 구한다. 3. 최대 아이템 수를 구한다

의 과정을 통해 문제를 해결 할 수 있습니다.

 

실제 구현은 아래와 같습니다.

import sys

n, m, r = list(map(int, sys.stdin.readline().rstrip().split()))

items = [0] + list(map(int, sys.stdin.readline().rstrip().split()))

graph = [[int(2e9)]*(n+1) for _ in range(n+1)]

for _ in range(r):
    a, b, l = list(map(int, sys.stdin.readline().rstrip().split()))
    graph[a][b] = l
    graph[b][a] = l
    
for i in range(n):
    graph[i+1][i+1] = 0
    
# done with input

# Floyd-Warshall
for k in range(1,n+1): # 거쳐가는 node
    for i in range(1,n+1): # 출발 node
        for j in range(1,n+1): # 도착 node
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

# find answer
ans_candidate = [-1]
for i in range(1,n+1):
    index_list = map(lambda x : x[0],list(filter(lambda x:x[1]<=m, enumerate(graph[i]))))
    ans_candidate.append(sum([items[t] for t in index_list]))
    
print(max(ans_candidate))