[백준/BOJ] 2458번: 키 순서

문제

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

2458번: 키 순서

해설

플로이드 와샬 알고리즘을 사용해서 문제를 해결하였다.

초기값을 저장할 배열을 BooleanArray로 선언하여 입력으로 알 수 있는 학생들끼리의 관계를 true로 해준다.

이 때 배열[i][j] = true라면, i가 j보다 작다가 되고, 배열[j][i] = true라면, j가 i보다 작다가 된다.

 

플로이드 와샬 알고리즘을 수행하며, 배열[i][k]와 배열[k][j]가 모두 참일 시, 배열[i][j]또한 참이 된다.

i가 k보다 작고 k는 j보다 작기 때문에, i는 j보다 작다가 된다.

플로이드 와샬 알고리즘을 모두 수행했다면, 처음 학생부터 모든 학생과 키를 비교할 수 있는지 수를 세본다.

비교할 수 있는 학생의 수가 자신을 제외한 n-1명이라면 자신의 키가 몇번째인지 알 수 있다.

코드

private lateinit var cmp: Array<BooleanArray>

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

    repeat(m) {
        val (s1, s2) = readLine().split(" ").map { it.toInt() }
        cmp[s1][s2] = true
    }

    floydWarshall(n)

    var ans = 0
    for(i in 1 .. n) {
        var cnt = 0
        for(j in 1 .. n) {
            if(cmp[i][j] || cmp[j][i]) cnt++
        }
        if(cnt == n - 1) ans++
    }
    println(ans)
}

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