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

🏆 문제 난이도
- Gold III

🔗 문제 링크
https://www.acmicpc.net/problem/2533

📝 문제 분석 & 접근

이 문제에서 각 노드는 사람을 나타내고, 간선은 친구 관계를 의미합니다.

여기서 핵심 규칙은 모든 일반인 친구는 적어도 한 명의 얼리어답터 친구를 가지고 있어야 한다는 것입니다.

 

접근 방식

트리 DP를 사용하기 위해, 각 노드(사람)에 대해 두 가지 상태를 정의하고, 그에 따른 최소 얼리어답터 수를 계산합니다.

1. 현재 노드가 얼리어답터인 경우: 현재 노드의 자식 노드는 얼리어답터이든 일반인이든 상관없습니다. 모든 자식 노드에 대해 '얼리어답터인 경우'와 '얼리어답터가 아닌 경우' 중 더 작은 값을 선택하여 더해줍니다.
2. 현재 노드가 얼리어답터가 아닌 경우: 문제의 규칙에 따라 모든 자식 노드는 반드시 얼리어답터가 되어야 합니다. 따라서 모든 자식 노드에 대해 '얼리어답터인 경우'의 값을 더해줍니다.

이 두 가지 상태에 대한 값을 dp 테이블에 저장하며, 재귀적으로 깊이 우선 탐색(DFS)을 통해 아래에서부터 위로(자식 노드에서 부모 노드로) 값을 계산해 나갑니다.

 

한 가지 주의할 점은, 친구 관계가 root가 있는게 아니다보니, 저 같은 경우에는 모든 사람이 root가 될 수 있다고 생각했습니다.

하지만, 문제에서는 root를 무조건 1번 노드로 잡고 있으니 저 같이 n개의 root의 모든 경우의 수를 구하는 실수는 없기 바랍니다...ㅠ

---

✨ 핵심 아이디어 : 트리 DP를 활용한 DFS

이 문제의 핵심은 트리의 리프 노드부터 시작하여 루트 노드까지 동적 계획법을 적용하는 것입니다.

DFS를 사용하면 자연스럽게 이 과정을 구현할 수 있습니다.

 

dfs(n) 함수는 노드 n을 기준으로 다음 두 가지 값을 계산합니다.

• dp[n][0] : 노드 n이 얼리어답터가 아닐 때 (일반인일 때) 필요한 최소 얼리어답터 수
• dp[n][1] : 노드 n이 얼리어답터일 때 필요한 최소 얼리어답터 수

어려운 내용이 아니니 나머지는 코드 주석과 함께 충분히 이해할 수 있을꺼라 생각합니다!

---

💻 코드

import java.io.StreamTokenizer
import kotlin.math.min

lateinit var graph : Array<ArrayList<Int>>
lateinit var visited : BooleanArray
lateinit var dp : Array<IntArray>

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    fun StreamTokenizer.nextInt(): Int{
        nextToken()
        return nval.toInt()
    }

    val n = nextInt()
    graph = Array(n+1) { ArrayList() }
    visited = BooleanArray(n+1)
    // [n][0]은 n번째 노드를 root 노드로 하는데, root 노드는 얼리아답터가 아닌 경우
    // [n][1]은 n번째 노드를 root 노드로 하는데, root 노드가 얼리아답터인 경우
    dp = Array(n+1) { IntArray(2) { 0 } }

    repeat(n-1) {
        val from = nextInt()
        val to = nextInt()
        graph[from].add(to)
        graph[to].add(from)
    }

    // 처음에는 root가 무조건 1이 아닐 수도 있는 거로 인지해서, 모든 노드를 root로 두고 반복문을 돌렸는데, 문제의 그래프를 보면 1번이 무조건 root인 것으로 가정하는 것 같다.
    dfs(1) // root 1 일때만 체크 해주면 됨
    println(min(dp[1][0], dp[1][1]))
}

fun dfs(n: Int) {
    visited[n] = true // 이거 안해주면 root 노드로 다시 돌아가서 무한 순환함.
    dp[n][0] = 0
    dp[n][1] = 1

    for (i in graph[n]) {
        if (!visited[i]){
            dfs(i) // 자식 노드 먼저 초기화
            dp[n][0] += dp[i][1]
            dp[n][1] += min(dp[i][0], dp[i][1])
        }
    }
}

 

+@) 참고로, 이렇게 데이터를 많이 받는 경우에는 readLine()이 아닌, Stringtokenizer 혹은 Streamtokenizer를 사용하면 시간과 메모리가 매우 많이 절약됩니다.

• readline을 쓴 경우

• streamtokenizer를 쓴 경우