[백준] 저울 (10159)(kotlin)

문제 설명

백준 10159번 문제 링크

입력 및 출력

» 입력

첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어진다. 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 공백을 사이에 두고 주어지며, 앞의 물건이 뒤의 물건보다 더 무겁다.

» 출력

여러분은 N개의 줄에 결과를 출력해야 한다. i 번째 줄에는 물건 i 와 비교 결과를 알 수 없는 물건의 개수를 출력한다.

예제 입출력(테스트케이스)

입력	출력
6 5 1 2 2 3 3 4 5 4 6 5	2 2 2 0 3 3
9 11 2 1 3 1 2 8 2 9 7 8 4 5 6 7 6 3 1 7 6 2 1 9	2 3 3 7 7 2 3 3 4

문제 풀이1 (실패)

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

    repeat(readLine().toInt()) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        // a -> b 대소관계 측정 가능
        matrix[a][b] = true
    }

    for (i in 1..N) {
        matrix[i][i] = true
        for (j in 1..N) {
            for (k in 1..N) {
                // i -> k (true)이고 k -> j (true)이면 i -> j (true)측정 가능
                if (matrix[i][k] && matrix[k][j]) {
                    matrix[i][j] = true
                }
            }
        }
    }

    for (i in 1..N) {
        var result = 0

        for (j in 1..N) {
            // i -> j 불가능하고, j -> i 불가능하면, i와 j는 대소비교 불가능
            if (!matrix[i][j] && !matrix[j][i]) result++
        }
        println(result)
    }
}

문제 풀이2 (성공)

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

    repeat(readLine().toInt()) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        // a -> b 대소관계 측정 가능
        matrix[a][b] = true
    }

    for (k in 1..N) {
        matrix[k][k] = true

        for (i in 1..N) {
            for (j in 1..N) {
                // i -> k (true)이고 k -> j (true)이면 i -> j (true)측정 가능
                if (matrix[i][k] && matrix[k][j]) {
                    matrix[i][j] = true
                }
            }
        }
    }

    for (i in 1..N) {
        var result = 0

        for (j in 1..N) {
            // i -> j 불가능하고, j -> i 불가능하면, i와 j는 대소비교 불가능
            if (!matrix[i][j] && !matrix[j][i]) result++
        }
        println(result)
    }
}