[백준] 1058 친구 Kotlin

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

1058번: 친구

처음에는 그래프를 이용한 dfs로 풀어야 하나 생각했으나 단순 반복문으로도 풀이가 가능해 보여서 간단하게 풀었다.

 

단순하게 for문을 돌려 모든 경우의 수를 구했다. 각 사람의 친구를 먼저 탐색하고 친구의 친구도 탐색해서 visited 배열에 저장한다. 자기 자신은 친구로 인정되지 않기 때문에 마지막에 자신을 false 처리하고 count 값을 구한다.

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    val n = readLine().toInt()
    val graph = Array(n) { mutableListOf<Int>() }
    var maxCount = 0

    repeat(n) {
        readLine().forEachIndexed { index, c ->
            if (c == 'Y' && n != index) {
                graph[it].add(index)
            }
        }
    }

    for (i in 0 until n) {
        var count = 0
        val visited = BooleanArray(n) { false }
        graph[i].forEachIndexed { index, j ->
            visited[j] = true
            graph[j].forEachIndexed { index2, k ->
                visited[k] = true
            }
        }
        visited[i] = false
        count = visited.count { it }
        maxCount = max(maxCount, count)
    }

    println(maxCount)
}

참고로 다른 사람들은 bfs를 이용해서 많이 풀었다.