Today I Learned

오늘도 코틀린 코테 연습!!!

플로이드

백준 11404번 https://www.acmicpc.net/problem/11404

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.
모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

• 입력
  5
  14
  1 2 2
  1 3 3
  1 4 1
  1 5 10
  2 4 2
  3 4 1
  3 5 1
  4 5 3
  3 5 10
  3 1 8
  1 4 2
  5 1 7
  3 4 2
  5 2 4
• 출력
  0 2 3 1 4
  12 0 15 2 5
  8 5 0 1 1
  10 7 13 0 3
  7 4 10 6 0

문제 풀이

• 문제 제목부터 플로이드 인 만큼 플로이드 워셜로 어떻게 문제를 푸냐를 시험하는 문제라 생각한다. 플로이드 워셜을 코틀린으로 구현해서 문제를 풀었다.

1. n, m을 입력으로 받아주고 2차원 배열을 이용해 graph를 초기화한다. 자기 자신으로 가는 비용은 0으로 초기화 한다.

2. 간선에 대한 정보를 repeat문으로 반아서 graph에 반영한다. 각 버스의 정보를 입력하는데, 시작 도시에서 도착 도시까지 최소 비용을 저장한다.

3. 플로이드워셜 알고리즘을 3중 중첩된 for문으로 구현해서 수행한다. 모든 노드 쌍의 최소 비용을 계산해 현재 노드를 거쳐가는 것이 비용이 더 적으면, 최소 비용을 업데이트 하는 방식으로 구현한다.

4. 2중 for문을 이용해 graph의 값을 출력해주면 완료!

Kotlin 코드

val INF = 11111111 // 충분히 큰 수

fun main() {
    val n = readln().toInt()
    val m = readln().toInt()

    val graph = Array(n) { IntArray(n) { INF } }

    repeat(n) { i ->
        graph[i][i] = 0
    }

    repeat(m) {
        val (a, b, c) = readln().split(" ").map { it.toInt() }
        graph[a - 1][b - 1] = minOf(graph[a - 1][b - 1], c)
    }

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

    for (i in 0 until n) {
        for (j in 0 until n) {
            print("${if (graph[i][j] == INF) 0 else graph[i][j]} ")
        }
        println()
    }
}