백준 14938번 서강그라운드 - 스위프트(Swift) 풀이

1. 모든 정점에 대해 각 정점에서 모든 정점으로 가는 거리를 플로이드 와샬 알고리즘을 사용하여 구한다.
2. 모든 정점에 대해 해당 정점과의 거리가 m이하인 정점들을 탐색하여 해당 정점에 낙하했을 때 얻을 수 있는 아이템 수를 구한다.
3. 2번에서 구한 값 중 최댓값을 출력한다.

---

1. 모든 정점에 대해각 정점에서 모든 정점으로 가는 거리를 플로이드 와샬 알고리즘을 사용하여 구한다.

 각 정점에 낙하하는 모든 경우를 고려한 뒤 최적해를 골라야 한다. 또한, 어떤 정점에 낙하했을 때 얻을 수 있는 아이템 수를 알려면, 해당 정점에서 나머지 정점으로의 거리를 전부 알아야 한다. 따라서 모든 정점에 대해 나머지 정점으로의 거리를 구하는 플로이드 와샬 알고리즘을 사용한다. N=100이므로 O(N^3)도 제한시간 내에 통과가 가능하다.

 

2. 모든 정점에 대해 해당 정점과의 거리가 m이하인 정점들을 탐색하여 해당 정점에 낙하했을 때 얻을 수 있는 아이템 수를 구한다.

 이제 각 정점에 대해 해당 정점과의 거리가 m이하인 정점들을 필터링해서 아이템 수의 합을 구한다.

 

3. 2번에서 구한 값 중 최댓값을 출력한다.

 2번에서 구한 각 경우 중 아이템을 최대로 얻을 수 있는 경우를 출력하면 된다.

 

---

import Foundation

let INF = 987654321
var n = 0, m = 0, r = 0
var dist = Array(repeating: Array(repeating: INF, count: 101), count: 101)
var items = [Int]()

func floydWarshall() {
    for k in 1...n {
        for i in 1...n {
            for j in 1...n {
                if dist[i][k] + dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }
}

func maxItemCount() -> Int {
    var result = 0
    
    for i in 1...n {
        var count = 0
        
        for j in 1...n {
            if dist[i][j] <= m { count += items[j] }
        }
        
        result = max(result, count)
    }
    
    return result
}

func solution() {
    var input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    n = input[0]
    m = input[1]
    r = input[2]
    
    items = [0] + readLine()!.split(separator: " ").map{ Int(String($0))! }
    
    for i in 1...n { dist[i][i] = 0 }
    for _ in 0..<r {
        input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        let start = input[0]
        let end = input[1]
        let weight = input[2]
        
        dist[start][end] = min(dist[start][end], weight)
        dist[end][start] = min(dist[end][start], weight)
    }
    
    floydWarshall()
    
    print(maxItemCount())
}

solution()