[백준 11404번][Kotlin] 플로이드

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

11404번: 플로이드

 

난이도 : 골드 4
태그 : 그래프이론, 플로이드 - 워셜

 

 

설명

문제의 제목처럼 플로이드 - 워셜 알고리즘을 이용해 해결할 수 있는 문제입니다.

 

플로이드 - 워셜 알고리즘의 기본격인 문제이니, 해당 알고리즘을 알고 계신다면 어렵지 않게 풀 수 있습니다.

 

저는 잘 몰라서 플로이드 - 워셜 알고리즘이 뭔지 찾아보고서야 풀었네요...ㅎㅎ

 

 

 

 

 

소스코드

값 입력과 테이블 준비

val br = BufferedReader(InputStreamReader(System.`in`))

val n = br.readLine().toInt() // 도시 개수
val m = br.readLine().toInt() // 버스 개수

val connect = Array(n) { Array(n) { Int.MAX_VALUE } }

repeat(m) {
    val abw = br.readLine().split(" ").map { it.toInt() } // 출발, 도착, 비용
    val a = abw[0] - 1
    val b = abw[1] - 1
    val w = abw[2]

    connect[a][b] = min(connect[a][b], w)
}
repeat(n) {
    connect[it][it] = 0
}

 

bufferedReader를 이용해 값을 입력받았고,

 

connect라는 이차원 배열을 만들어,

a도시로부터 b 도시로 가는 비용을 connect[a][b]와 같이 저장했습니다.

 

a 도시에서 b 도시로 가는 버스가 없을 경우, 갈 수 있는 방법이 존재하지 않으므로

값을 Int.MAX_VALUE로 둡니다.

 

또, a도시에서 a도시로 가는 버스는 없으므로, 0으로 초기화 해줍니다.

 

 

플로이드 - 워셜

for (k in 0 until n) {
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (connect[i][k] == Int.MAX_VALUE || connect[k][j] == Int.MAX_VALUE) continue
            if (connect[i][j] > connect[i][k] + connect[k][j]) connect[i][j] = connect[i][k] + connect[k][j]
        }
    }
}

 

플로이드 - 워셜 알고리즘을 적용합니다.

 

 

 

해당 알고리즘을 설명하면 다음과 같습니다.

 

a 도시에서 c 도시로 가는 비용이 10이 듭니다.

a 도시에서 b 로 가는 비용이 3이며, b 도시에서 c 도시로 가는 비용이 5일때,

a도시에서 c로 가는 비용(10) 보다 a 도시에서 b를 거쳐 c로 가는 비용(3+5=8)이 더 낮은 코스트를 보입니다.

 

위 코드상에선 i를 시작점, j를 도착점, k를 경유점으로 보고

 

connect[i][j] (i에서 j로 가는 비용)과 connect[i][k] + connect[k][j] (i에서 k를 거쳐 j로 가는 비용)을 비교하여,

더 저렴한 비용으로 테이블을 갱신하면 됩니다.

 

 

단, i -> k, k -> j 중 둘 중 하나라도 갈 수 있는 버스가 없을 경우,

해당 값은 Int.MAX_VALUE를 갖고 있기에, 오버플로우가 발생합니다.

 

따라서, i -> k, k -> j 둘 중 하나라도 갈 수 있는 버스가 존재하지 않을 경우 continue를 통해 다음 반복회차로 넘어갑니다.

 

 

 

출력

connect.forEach { it1 ->
    it1.forEach { it2 ->
        print("${if (it2 == Int.MAX_VALUE) 0 else it2} ")
    }
    println()
}

갈 수 있는 방법이 존재하지 않을 경우 (Int.MAX_VALUE)일 경우 0을, 그렇지 않다면 해당 값을 출력해줍니다.

 

 

 

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val n = br.readLine().toInt() // 도시 개수
    val m = br.readLine().toInt() // 버스 개수

    val connect = Array(n) { Array(n) { Int.MAX_VALUE } }

    repeat(m) {
        val abw = br.readLine().split(" ").map { it.toInt() } // 출발, 도착, 비용
        val a = abw[0] - 1
        val b = abw[1] - 1
        val w = abw[2]

        connect[a][b] = min(connect[a][b], w)
    }
    repeat(n) {
        connect[it][it] = 0
    }

    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (connect[i][k] == Int.MAX_VALUE || connect[k][j] == Int.MAX_VALUE) continue
                if (connect[i][j] > connect[i][k] + connect[k][j]) connect[i][j] = connect[i][k] + connect[k][j]
            }
        }
    }

    connect.forEach { it1 ->
        it1.forEach { it2 ->
            print("${if (it2 == Int.MAX_VALUE) 0 else it2} ")
        }
        println()
    }
}

 

 

후기

최단경로 알고리즘이라고 하면, 다익스트라만 떠올렸다가

플로이드 - 워셜이라는 모든 정점에서 다른 모든 정점에 대한 최단 경로 알고리즘이 있다는 것을 알게 된 문제였습니다.