[백준] 키 순서 (2458)(kotlin)

문제 설명

백준 2458번 문제 링크

입력 및 출력

» 입력

첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.

» 출력

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.

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

입력	출력
6 6 1 5 3 4 5 4 4 2 4 6 5 2	1
6 7 1 3 1 5 3 4 5 4 4 2 4 6 5 2	2
6 3 1 2 2 3 4 5	0

문제 풀이1

fun main() = with(System.`in`.bufferedReader()) {
    val (N, M) = readLine().split(" ").map { it.toInt() }
    val matrix = Array(N + 1) { BooleanArray(N + 1) }

    repeat(M) {
        val (s, e) = readLine().split(" ").map { it.toInt() }
        matrix[s][e] = true
    }

    for (k in 1 until N + 1) {
        for (i in 1 until N + 1) {
            matrix[i][i] = true
            for (j in 1 until N + 1) {
                if (matrix[i][k] && matrix[k][j]) matrix[i][j] = true
            }
        }
    }

    var result = 0
    for (i in 1 until N + 1) {
        for (j in 1 until N + 1) {
            if (!matrix[i][j] && !matrix[j][i]) break
            if (j == N) result++
        }
    }

    println(result)
}

문제 풀이1 (시뮬레이션)