[백준 1613] [Kotlin] 역사

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

1613번: 역사

 

난이도 : 골드 3
태그 : 그래프 이론, 플로이드-워셜

 

 

1. 설명

플로이드 워셜 알고리즘을 응용하여 풀 수 있을 것 같습니다.

플로이드 워셜 알고리즘을 잘 모르겠다면, 아래 포스팅을 참고해주세요.

https://uknowblog.tistory.com/39

[백준 11404번][Kotlin] 플로이드

 

 

플로이드 워셜 알고리즘은 최단경로를 구하는 알고리즘이지만,

순서를 구할 때에도 응용할 수 있습니다.

 

 

 

2. 소스코드

      

      

      

    
    

      <kotlin />
    
import java.util.*

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

    val arr = Array(n + 1) { Array(n + 1) { 987654321 } }

    repeat(k) {
        val st = StringTokenizer(readLine())
        val from = st.nextToken().toInt()
        val to = st.nextToken().toInt()
        arr[from][to] = 1
    }

    for (k in 1..n) {
        for (i in 1..n) {
            for (j in 1..n) {
                if (arr[i][j] > arr[i][k] + arr[k][j]) {
                    arr[i][j] = arr[i][k] + arr[k][j]
                }
            }
        }
    }

    val sb = StringBuilder()
    repeat(readLine().toInt()) {
        val st = StringTokenizer(readLine())
        val from = st.nextToken().toInt()
        val to = st.nextToken().toInt()
        
        if (arr[from][to] == arr[to][from]) sb.append("0")
        else if (arr[from][to] > arr[to][from]) sb.append("1")
        else sb.append("-1")
        sb.append("\n")
    }

    print(sb)
}

 

일반적인 플로이드 워셜 알고리즘과 같으나,

a와 b의 순서관계가 주어진다면 arr[a][b]를 1로 만들어줍니다.

이후, 플로이드 워셜 알고리즘을 적용시키고,

플로이드 워셜이 끝나면

arr[a][b]와 arr[b][a]의 값을 비교합니다.

arr[a][b]가 arr[b][a]보다 크다면,  b의 사건이 먼저 일어난 것입니다. 따라서 1을,

arr[b][a]가 arr[a][b]보다 크다면, a의 사건이 먼저 일어난 것이므로 -1을,

arr[a][b]와 arr[b][a]가 같다면 순서를 가릴 수 없으므로 0을 출력합니다.

 

 

3. 후기

그래프는 언제 해도 재밌습니다.