백준 1613. 역사

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

1613번: 역사

 

fun Array<IntArray>.floydWarshall(): Array<IntArray> {
    val n = this.size - 1

    for (k in 1..n) {
        for (i in 1..n) {
            for (j in 1..n) {
                if (i == j || this[i][k] == Int.MAX_VALUE || this[k][j] == Int.MAX_VALUE) {
                    continue
                }

                if (this[i][j] > this[i][k] + this[k][j]) {
                    this[i][j] = this[i][k] + this[k][j]
                }
            }
        }
    }

    return this
}

fun main(args: Array<String>) {
    val (n, k) = readln().split(" ").map { it.toInt() }

    val graph = Array(n + 1) { IntArray(n + 1) { Int.MAX_VALUE } }.apply {
        repeat(k) {
            val (a, b) = readln().split(" ").map { it.toInt() }

            this[a][b] = 1
        }
    }.floydWarshall()

    repeat(readln().toInt()) {
        val (x, y) = readln().split(" ").map { it.toInt() }

        if (graph[x][y] != Int.MAX_VALUE) {
            println(-1)
        } else if (graph[y][x] != Int.MAX_VALUE) {
            println(1)
        } else {
            println(0)
        }
    }
}

 

풀이

각 정점에서 갈 수 있는 모든 정점들을 그래프로 표현한 뒤, a에서 b로 갈 수 있으면 -1, b에서 a로 갈 수 있으면 1, 둘 다 못가면 0을 출력하면 된다. (a, b = 각 정점) 모든 정점에서 갈 수 있는 알고리즘으로 플로이드 워셜이 있어서 해당 알고리즘을 적용하면 해결 할 수 있다.