[백준] 역사 (1613)(kotlin)

문제 설명

백준 1613번 문제 링크

입력 및 출력

» 입력

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

» 출력

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

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

입력	출력
5 5 1 2 1 3 2 3 3 4 2 4 3 1 5 2 4 3 1	0 -1 1

문제 풀이1

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

    repeat(k) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        matrix[a][b] = true
    }

    for (k in 1..n) {
        for (i in 1..n) {
            for (j in 1..n) {
                if (matrix[i][k] && matrix[k][j]) {
                    matrix[i][j] = true
                }
            }
        }
    }

    repeat(readLine().toInt()) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        if (a !in 1..n || b !in 1..n) println(0)
        else if (matrix[a][b]) println(-1)
        else if (matrix[b][a]) println(1)
        else println(0)
    }
}

문제 풀이2

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

    repeat(k) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        matrix[a][b] = -1
        matrix[b][a] = 1
    }

    for (k in 1..n) {
        for (i in 1..n) {
            for (j in 1..n) {
                if (matrix[i][j] == 0) {
                    if (matrix[i][k] == -1 && matrix[k][j] == -1) matrix[i][j] = -1
                    if (matrix[i][k] == 1 && matrix[k][j] == 1) matrix[i][j] = 1
                }
            }
        }
    }

    repeat(readLine().toInt()) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        println(matrix[a][b])
    }
}