[백준/BOJ] 10159번: 저울

문제

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

10159번: 저울

해설

전형적인 플로이드 와샬 알고리즘 문제이다.

플로이드 와샬 알고리즘을 사용하는 문제이므로 우선 물건의 개수만큼의 이중 배열을 선언한다.

나는 이 배열을 boolean 배열로 하였지만, 다른 배열로 하여도 설정만 잘하면 크게 상관없다.

 

물건 쌍의 개수를 입력받으면, 배열에서의 그 인덱스를 true로 한다.

이는 양방향이 아닌 1 > 2처럼 단방향이므로 한쪽으로만 정의를 해주면 된다.

플로이드 와샬의 수행이 끝났다면, 이중 배열을 보며 각 행마다 몇 개의 false가 존재하는지 세면 된다.

만약 map[1][2] = false더라도, map[2][1] = true일 수 있다. 이처럼 되면 서로 연결이 돼있는 것이므로 모두 false일 때만 개수를 세준다.

이때 자기 자신 ex) 1 > 1과 같은 입력은 없으니 행과 열이 같을 때는 고려하지 않는다.

코드

private lateinit var map: Array<BooleanArray>

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val pairCnt = readLine().toInt()
    map = Array(n + 1) { BooleanArray(n + 1) }

    repeat(pairCnt) {
        val (from, to) = readLine().split(" ").map { it.toInt() }
        map[from][to] = true
    }

    floyd(n)

    val sb = StringBuilder()
    for(i in 1 .. n) {
        var cnt = 0
        for(j in 1 .. n) {
            if(i == j) continue
            if(!map[i][j] && !map[j][i]) cnt++
        }
        sb.append("${cnt}\n")
    }

    println(sb.toString())
}

private fun floyd(n: Int) {
    for(k in 1 .. n) {
        for(i in 1 .. n) {
            for(j in 1 .. n) {
                if(map[i][k] && map[k][j]) map[i][j] = true
            }
        }
    }
}