[백준 2458번] [Kotlin] 키 순서

 

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

2458번: 키 순서

 

난이도 : 골드 4
태그 : 그래프 이론, 그래프 탐색, 플로이드 워셜

 

 

설명

https://uknowblog.tistory.com/168

[백준 10159번] [Kotlin] 저울

 

예전에 포스팅했던 저울 문제와 비슷한 문제입니다.

키 순서를 확인하기 위해선, 특정 학생과 다른 모든 학생들의 키 순서를 비교할 수 있어야 하므로,

플로이드 - 워셜 알고리즘을 사용해 비교 가능한 지 확인해야 합니다.

 

 

소스코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    // 학생의 수 n, 키 비교 횟수 m
    val (n, m) = readLine().split(" ").map { it.toInt() }

    val weight = Array(n + 1) { Array(n + 1) { 0 } }

    repeat(m) {
        val st = StringTokenizer(readLine())
        val a = st.nextToken().toInt()
        val b = st.nextToken().toInt()
        weight[a][b] = 1
    }

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

    var ans = 0

    for (i in 1..n) {
        var cnt = 0

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

 

코드분석

1. 학생들의 비교 관계를 담은 weight를 생성 (초기값 0)
2. 플로이드-워셜 알고리즘 수행. 학생 a의 키가 b보다 크다면 weight[a][b]를 1로 설정. 얼마나 큰지 비교하는게 아니라, 비교할 수 있느냐가 중요하므로 0/1로 하여도 무방
3. weight[i][j] == 1, weight[j][i] == 1이면 두 학생의 키를 비교할 수 있음을 의미하며, 자기 자신을 제외한 모든 학생과 비교할 수 있으면 (weight[i][j] == 1, weight[j][i] == 1의 개수가 n-1) 해당 학생의 키 순서를 알 수 있음을 의미
4. 키 순서를 알 수 있는 학생의 수를 출력

 

 

후기

저번에 저울 문제를 풀고, 플로이드 워셜을 응용한 문제를 풀고 있습니다.

한 알고리즘을 이해하기 위해선, 해당 알고리즘을 응용한 문제를 집중적으로 풀어보는 것도 나쁘진 않은 것 같습니다.

다만, 한동안 안풀다보면 까먹게 되니 긴가민가 할 즈음에 다시 풀어봐야 합니다.