[백준/BOJ] 1058번: 친구

문제

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

1058번: 친구

해설

2-친구가 되기 위한 조건은 다음과 같다.

• 서로 친구이다.
• 한다리 건너 친구이다.

이 문제는 플로이드 와샬 알고리즘을 이용하여 해결하였다.

우선 자기 자신과는 친구를 맺을 수 없으므로 0으로, 나머지는 INF(987654321)로 초기화하였다.

후에 입력으로 Y값이 들어온다면 그 인덱스를 1로 선언하였다.

 

이제 플로이드 와샬 알고리즘을 수행시켜 몇다리를 건너 아는 사이인지를 모두 구한다.

플로이드 와샬 알고리즘을 모른다면 이 글을 읽어보자.

 

알고리즘 수행이 끝났으면 각각 2-친구가 몇명이 있는지 세보면 된다.

i == j 가 아니면서 arr[i][j] <= 2라면 2-친구에 해당한다.

여기서 가장 유명한 사람의 2-친구를 출력하면 된다.

코드

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

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

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    arr = Array(n) { IntArray(n) }

    repeat(n) { i ->
        repeat(n) { j ->
            if(i == j) arr[i][j] = 0
            else arr[i][j] = INF
        }
    }

    repeat(n) { i ->
        val stat = readLine().toCharArray()
         repeat(n) { j ->
             if(stat[j] == 'Y') arr[i][j] = 1
         }
    }

    floyd(n)

    var max = 0
    for(i in 0 until n) {
        var cnt = 0
        for(j in 0 until n) {
            if(i == j) continue
            if(arr[i][j] <= 2) cnt++
        }

        max = max(cnt, max)
    }

    println(max)
}

private fun floyd(n: Int) {
    for(k in 0 until n) {
        for(i in 0 until n) {
            for(j in 0 until n) {
                if(i == j || i == k || j == k) continue
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])
            }
        }
    }
}