[백준 10159번] [Kotlin] 저울

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

10159번: 저울

 

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

 

 

설명

각 물건들의 비교결과가 주어질 때, 각 물건과 비교결과를 알 수 없는 물건의 개수를 출력해야 합니다.

저는 처음에, 특정 값에 따른 비교가 아니라, 두 물건간의 우열이 주어진 상태라는 것만 보고,

위상정렬을 떠올려 바로 위상정렬로 풀이를 진행하려 했으나,

비교결과를 알 수 없는 물건의 개수를 출력하는게 생각보다 어렵더군요...

뭐지..? 위상정렬이 아닌가? 하는 생각에 문제 태그를 슬쩍 봤는데, 플로이드 - 워셜 알고리즘이였습니다.

 

플로이드 워셜을 이런 방법으로도 사용할 수 있겠구나 하는 생각에 놀라워하며, 바로 코딩을 시작했습니다.

 

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

https://uknowblog.tistory.com/39

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

 

 

소스코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt() // 물건의 개수
    val m = readLine().toInt() // 순서 쌍의 개수

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

    for (i in 1..n) {
        weight[i][i] = 0
    }

    repeat(m) {
        val st = StringTokenizer(readLine())
        val o1 = st.nextToken().toInt()
        val o2 = st.nextToken().toInt()

        weight[o1][o2] = 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
                }
            }
        }
    }

    val sb = StringBuilder()

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

        for (j in 1..n) {
            if (i != j && weight[i][j] == 0 && weight[j][i] == 0) cnt++
        }
        sb.append(cnt).append("\n")
    }

    print(sb)
}

 

 

코드분석

1. 물건과의 비교값 weight을 생성한다. 초기값은 0이다.
2. 물건과의 비교값이 있을 때, weight을 1로 설정한다. 얼마만큼 더 무겁냐를 보는 것이 아닌, 비교를 할 수 있는가를 보는 것이기 때문에 비교 가능 - 1, 비교 불가 - 0 으로 두어도 상관 없다.
3. 플로이드 - 워셜 알고리즘을 적용한다.
   1. 다른 물건을 거쳐 비교 가능할 때, 시작 물건과 대상 물건의 weight을 1로 만든다.
4. weight[i][j], weight[j][i] 모두 0이면 서로 비교가 불가능 한 것이므로, 카운팅하여 출력한다.

 

 

후기

플로이드 워셜의 새로운 활용법을 배운 문제였습니다.