BOJ 21940_가운데서 만나기

문제

풀이

package solve_21940

import java.io.StreamTokenizer
import java.util.*

private const val INF = 1000000000

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    val n = input()
    val m = input()
    val graph = Array(n+1){
        IntArray(n+1){
            INF
        }
    }

    for(i in 1..n){
        graph[i][i] = 0
    }

    repeat(m){
        val s = input()
        val e = input()
        val t = input()

        graph[s][e] = t
    }

    for(i in 1..n){
        for (j in 1..n){
            for(k in 1..n){
                graph[j][k] = minOf(graph[j][i] + graph[i][k] , graph[j][k])
            }
        }
    }

    val k = input()
    val friendsCity = IntArray(k){
        input()
    }
    val answer = ArrayList<Int>()
    var nowTime = Int.MAX_VALUE
    for(city in 1..n){
        var max = 0
        friendsCity.forEach{
            max = maxOf(graph[city][it] + graph[it][city], max)
        }

        if(nowTime > max){
            nowTime = max
            answer.clear()
            answer.add(city)
        } else if(nowTime == max){
            answer.add(city)
        }
    }

    val sb = StringBuilder()
    answer.forEach{
        sb.append("$it ")
    }

    println(sb)
}

사용 알고리즘

최단거리 탐색 / 플로이드 워셜

플로이드 워셜 알고리즘을 사용하여 각 도시에서 다른 모든 도시까지의 최단 거리를 구하였다.

하나의 도시를 선택하여 친구가 있는 각 도시까지의 왕복거리를 계산한 후 그중 가장 큰 값을 가지는 왕복거리를 저장 한 후 다른도시의 결과와 비교하며 그중 최솟값을 가지는 도시를 선택한다.

이때 만약 최솟값이 같은 경우라면 해당하는 도시를 오름차순으로 보여줘야 한다.
값이 갱신 되는 경우는 answer 배열을 clear하여 값이 초기화 되게 하고 최솟값이 같은 경우라면 이전의 arrayList에 값을 추가해 준다.

도시의 탐색 순서를 1부터 n까지 for문을 통해 순회하므로 별도의 정렬을 진행할 필요 없이 순서대로 값은 들어가게 된다.

모든 도시에 대한 결과를 확인 후 저장된 answer의 값을 StringBuilder로 출력하였다.