백준 14938 서강그라운드

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

시작 위치에서 m 범위 이하의 모든 아이템들의 개수의 합 중 최대를 구하는 문제이다.

그래서 처음엔 각 위치에서 bfs를 통해 m범위 이하의 아이템들을 더하는 방법을 생각하였다.

하지만 문제에서 주어지는 연결 구조가 그래프라는 언급이 없었고, 그에 따라 순환 구조가 생길 수 있다는 점을 간과했다

만약 순환 구조가 생긴다면 문제가 발생한다.

1번을 시작점이라 하면, 2번과 4번 정점을 방문체크하고 큐에 넣는다.

1 - 2 - 3 경로가 가장 짧은 3번 정점에서는 문제가 없지만 5번 정점에서 문제가 생긴다.

만약 m이 10이라 하면, 1 - 4 - 5 경로를 통해서는 도달할 수 없고 1 - 2 - 4 - 5 경로를 통해서 5번에 도달할 수 있다.

하지만 bfs의 특성을 생각해 본다면??

• 1번 정점에서 2번과 4번을 큐에 넣음
• 2번을 큐에서 뽑고 방문 체크 이후 연결된 3번과 4번을 큐에 넣음
• 4번을 큐에서 뽑고 방문 체크 이후 5번을 넣지 않음(거리 11이므로)
• 다음 3번을 뽑아 체크하고, 4번을 다시 뽑지만 방문 체크가 되어있어 1 - 2 - 4 - 5 경로가 스킵됨.

+) 글을 작성하는 중 PriorityQueue를 이용하면 가능할 것 같기도 한데 시도해 보고 추후 추가하겠다.

따라서 이 경우에 사용할 수 있는 알고리즘이 2가지가 있다.

1. 각 점에서 다익스트라 알고리즘을 통해 최소 경로를 구하고, m 이하인 정점들의 아이템 개수를 더한 값들 중 최댓값을 출력함.

2. 플로이드 알고리즘을 통해 최소 경로에 대한 이차원 배열을 구한 후 m 이하인 거리의 아이템 합 중 최댓값을 출력함.

뭔가 플로이드로 이차원 배열을 구해 놓으면, 추가로 다시 구할 필요 없이 해당 배열을 탐색하게 되는 것 같아 플로이드로 구현하였다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (n, m, r) = readLine().split(' ').map{it.toInt()}

    val items = readLine().split(' ').map { it.toInt() }

    val floyd = Array(n + 1) { IntArray(n + 1){123456789} }

    for(i in 1..r){
        val (a, b, l) = readLine().split(' ').map{it.toInt()}
        floyd[a][b] = l
        floyd[b][a] = l
    }

    for(i in 1..n){
        for(j in 1..n){
            if(i == j){
                floyd[i][j] = 0
            }
        }
    }

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

    var answer = 0
    for(i in 1..n){
        var sum = 0
        for(j in 1..n){
            if(floyd[i][j] <= m)
                sum += items[j - 1]
        }
        if(answer < sum) answer = sum
    }

    print(answer)
}