백준 - 친구

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/1058

 

[문제 설명]

가장 유명한 사람(2-친구가 가장 많은 사람)의 친구수를 출력하시오.
단, 2-친구란? 직접 친구이거나, 친구의 친구여야 한다.

 

[접근 방법]

친구의 친구까지가 친구입니다.

즉, 현재 사람을 기준으로 경로의 길이가 2이하인 노드의 개수를 구하는 것입니다.

2-친구는 간단하게 이중 for문으로 구하면 됩니다.
그러나, 3-친구나 4-친구로 확장 가능성을 생각하면 재귀를 사용하는 것이 좋습니다.

시간복잡도는 사람의수^2 = O(N^2).

만약 사람 수를 H, 깊이를 N으로 둘 경우 O(H^N)이 됩니다.

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val friendStatus = Array(n) { BooleanArray(n) }
    repeat(n) { row ->
        readLine().forEachIndexed { col, c ->
            when (c) {
                'Y' -> friendStatus[row][col] = true
            }
        }
    }

    val isFriendOfRow = Array(n) { BooleanArray(n) }
    // n번째 친구를 구하라.
    fun getNthFriend(n: Int, currentN: Int, currentRow: Int, pivotRow: Int) {
        if (currentN > n) {
            return
        }

        for (col in friendStatus[currentRow].indices) {
            // if : 친구면
            if (friendStatus[currentRow][col]) {
                // if : 자기 자신은 체크 안해도되므로 continue
                if (pivotRow == col) {
                    continue
                }

                isFriendOfRow[pivotRow][col] = true
                // 현재 거리보다 1 떨어진 친구 구하기.
                getNthFriend(n, currentN + 1, currentRow = col, pivotRow = pivotRow)
            }
        }
    }

    for (i in 0 until n) {
        getNthFriend(n = 2, currentN = 1, currentRow = i, pivotRow = i)
    }

    // 구하고자 하는 친구 인원 수
    var answer = Int.MIN_VALUE
    for (r in isFriendOfRow.indices) {
        var cntOfFriend = 0
        for (c in isFriendOfRow[r].indices) {
            if (isFriendOfRow[r][c]) {
                cntOfFriend++
            }
        }

        // 친구 최댓값을 구한다.
        answer = answer.coerceAtLeast(cntOfFriend)
    }

    println(answer)
}