[백준/코틀린] 11403번: 경로 찾기

링크

11403번: 경로 찾기

풀이

주어진 인접 행렬에 플로이드-워셜(Floyd–Warshall) 알고리즘을 적용합니다.
중간 정점 k를 경유한 i → k → j 경로가 존재하면 i → j도 도달 가능하므로,
이 규칙을 반복해 모든 정점 쌍의 경로 존재 여부를 갱신합니다.

[실전 알고리즘] 0x1C강 - 플로이드 알고리즘

코드

fun main() {
    val n = readln().toInt()
    val graph = List(n) { readln().split(" ").map { it.toInt() }.toMutableList() }

    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                graph[i][j] = graph[i][j] or (graph[i][k] and graph[k][j])
            }
        }
    }

    graph.forEach { println(it.joinToString(" ")) }
}