[백준/BOJ] 1613번: 역사

문제

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

1613번: 역사

해설

n개의 사건들의 전후 관계가 주어진다. 이를 통해 두 개의 사건의 전후 관계를 알아낼 수 있는지, 안다면 먼저 일어났는지, 후에 일어났는지를 알아내면 된다.

플로이드 와샬 알고리즘을 이용하면 모든 사건들의 전후 관계를 한번의 알고리즘 수행으로 알아낼 수 있다.

 

전후 관계를 표시할 배열들을 초기값(INF = 987654321이라 하자.)으로 선언해준다.

이때 같은 사건(i == j)끼리는 전후관계가 존재하지 않으므로 0으로 처리해주었다.

이제 전후 관계에 대해 입력을 받으며 이 인덱스의 값을 1로 바꿔주었다.

모두 처리가 되었다면, 플로이드 와샬 알고리즘을 통해 전후 관계를 확인한다.

 

이제 사건의 전후 관계를 알아야 한다.

전에 나온 사건을 before, 후에 나온 사건을 after라고 하면, arr[before][after]과 arr[after][before]이 모두 INF의 값을 가지고 있다면, 이 둘의 전후 관계를 알 수 없다. 둘이 연결되는 사건이 없기 때문이다.

arr[before][after]가 특정 값을 가지며, arr[after][before]가 INF라면 앞에 있는 사건이 먼저 일어난 것이므로 -1을 출력해주고, 이 반대라면 뒤에 있는 사건이 먼저 일어난 것이므로 1을 출력해주면 된다.

코드

import kotlin.math.min

private lateinit var arr: Array<IntArray>
private const val INF = 987654321

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

    for(i in 1 until n + 1) {
        for(j in 1 until n + 1) {
            if(i == j) arr[i][j] = 0
            else arr[i][j] = INF
        }
    }

    repeat(k) {
        val (accident1, accident2) = readLine().split(" ").map { it.toInt() }
        arr[accident1][accident2] = 1
    }

    floyd(n)

    val wantKnow = readLine().toInt()
    repeat(wantKnow) {
        val (before, after) = readLine().split(" ").map { it.toInt() }

        if(arr[before][after] == INF && arr[after][before] == INF) println(0)
        else if(arr[before][after] != INF) println(-1)
        else if(arr[after][before] != INF) println(1)
    }
}

private fun floyd(n: Int) {
    for(k in 1 .. n) {
        for(i in 1 .. n) {
            for(j in 1 .. n) {
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])
            }
        }
    }
}