[백준/BOJ] 2660번: 회장뽑기

문제

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

2660번: 회장뽑기

해설

두 회원이 친구 사이라면 1, 친구의 친구 사이라면 2, 친구의 친구의 친구 사이라면 3 ... 과 같이 숫자가 증가한다.

예를 들어 1, 2, 3의 회원이 있을 때, 1번 회원과 2번 회원이 친구 사이이고, 2번 회원과 3번 회원이 친구 사이라면 1번 회원과 3번 회원은 친구의 친구 사이이므로 2의 값을 가지게 된다.

즉, 한 다리를 거쳐 알 수 있다는 것이므로 플로이드 와샬 알고리즘을 사용하면 된다.

문제의 예시를 플로이드 와샬 알고리즘을 수행하고 나면 다음과 같은 표를 얻을 수 있다.

따라서 각 회원들의 점수는 다음과 같다.

회장은 이 점수가 가장 적은 사람이 될 수 있다.

이 표에서 가장 낮은 점수는 2이고, 후보는 3명이 된다.

회장 후보 번호는 2, 3, 4번이 된다.

1번부터 시작하여 차례로 확인을 하며 리스트에 집어넣으므로 따로 정렬을 할 필요없다.

코드

import kotlin.math.max
import kotlin.math.min

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

fun main() = with(System.`in`.bufferedReader()) {
    val memberCnt = readLine().toInt()

    member = Array(memberCnt + 1) { IntArray(memberCnt + 1) { INF } }
    for(i in 1 .. memberCnt) {
        for(j in 1 .. memberCnt) {
            if(i == j) member[i][j] = 0
        }
    }

    while(true) {
        val (member1, member2) = readLine().split(" ").map { it.toInt() }
        if(member1 == -1 && member2 == -1) break

        member[member1][member2] = 1
        member[member2][member1] = 1
    }

    floyd(memberCnt)

    var min = Integer.MAX_VALUE
    val candidate = ArrayList<Int>()

    for(i in 1 .. memberCnt) {
        var max = Integer.MIN_VALUE
        for(j in 1 .. memberCnt) {
            max = max(max, member[i][j])
        }

        if(max < min) {
            min = max
            candidate.clear()
            candidate.add(i)
        }
        else if(max == min) candidate.add(i)
    }

    println("$min ${candidate.size}")
    candidate.forEach { print("$it ") }
}

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