[백준 - 2533] 사회망 서비스(SNS)

문제링크

• Bottom-up 방식으로 진행합니다.
• 각 node는 기본적으로 얼리어답터 일때와 아닐때로 구분할 수 있습니다.
• 얼리어답터이면 dp[node][1] = 1 으로 할당하고, 얼리어답터가 아니면 dp[node][0] = 0 으로 할당합니다.
• 현재 node가 얼리어답터가 아니면 자식들이 반드시 얼리어답터 이어야 하기 때문에 dp[node][0] 에 dp[child][1] 값을 전부 더해줍니다.
• 현재 node가 얼리어답터이면 자식들이 얼리어답터여도 되고 얼리어답터가 아니여도 되기 때문에 자식들의 dp[child][0], dp[child][1] 중 작은 값을 더해줍니다.
• dfs를 통해 위 모든 과정을 반복하고 최상위 root의 dp값 중 작은 값을 출력합니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import kotlin.math.min

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter
private lateinit var graph: Array<MutableList<Int>>
private lateinit var dp: Array<Array<Int>>
private lateinit var visited: Array<Boolean>

fun main() {
    bufferedReader = System.`in`.bufferedReader()
    bufferedWriter = System.out.bufferedWriter()

    val n = bufferedReader.readLine().toInt()
    graph = Array(n + 1) { mutableListOf() }
    dp = Array(n + 1) { Array(2) { 0 } }
    visited = Array(n + 1) { false }

    repeat(n - 1) {
        val (u, v) = bufferedReader
            .readLine()
            .split(" ")
            .map { it.toInt() }
        graph[u].add(v)
        graph[v].add(u)
    }

    dfs(1)
    bufferedWriter.write("${min(dp[1][0], dp[1][1])}")

    bufferedReader.close()
    bufferedWriter.close()
}

fun dfs(root: Int) {
    visited[root] = true
    dp[root][0] = 0
    dp[root][1] = 1

    for (child in graph[root]) {
        if (!visited[child]) {
            dfs(child)
            dp[root][0] += dp[child][1]
            dp[root][1] += min(dp[child][0], dp[child][1])
        }
    }
}

주석 없는 코드를 만들기 위해 노력하는 개발자입니다.

혹시라도 의도가 분명하지 않아보이는 (이해가 되지 않는) 코드가 있으시다면 편하게 답변 달아주시면 정말 감사하겠습니다.