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

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

 

DP & DFS

 

트리인 그래프의 노드간 연결 정보가 간선개수(= 노드개수-1) 만큼 주어지고,

모든 노드는 얼리어답터이거나 아니거나 일 때, 내가 얼리어답터면 내 친구들에게 정보를 전파할 수 있음.

그래프의 모든 노드가 정보를 전파 받을 수 있으려면 최소 몇명이 얼리어답터여야 하는지.

구하는 문제

 

 

접근방법

DP랑 DFS 같이 쓰는거 생각해내기까지가 어려운 것 같음..블로그 보고 이해하고 풀이함

 

key 고려사항

1. 무방향 그래프 처럼 인접 그래프를 만든다.

2. DP 배열은 노드수 * 2 이고,

[N][0] : N 번째 노드가 얼리어답터인 경우 최소 얼리어답터수

[N][1] : N 번째 노드가 얼리어답터가 아닌 경우 최소 얼리어답터수

이다.

3. visit 배열은 부모노드인지 아닌지 판별하기 위함 (부모노드의 값은 내 위치의 최소 얼리어답터수에 포함하지 않음)

4. 부모노드는 어느 노드가 되어도 상관없음. 처음 dfs 탐색을 시작하는 노드 위치가 부모노드가 됨

 

여기서 알 수 있듯이 여기서 sub-problem이 "내가 얼리어답터일때/아닐때 '나 부터 내 아래로 있는 모든 자식 노드 포함' 필요한 최소 얼리어답터 수 구하기" 였다.

DFS로 탐색하면서 각 노드의 DP값을 한 depth씩 만 생각한다. 무슨 말이냐면

그래프에 나랑 내 자식노드들만 있다고 생각하고 모두가 지식을 전파 받으려면 어떻게 해야하는지 생각해야함.

그러면 내가 얼리어답터인 경우 -> 내 자식노드들 까지는 (내 직속 친구들(?) 까지는) 얼리어답터 아니어도 됨 (얼리어답터 여도 됨 - 둘 중 적은 값)

내가 얼리어답터가 아닌 경우 -> 내 자식노드들이 모두 얼리어답터여야 됨

 

이런식으로 생각하면

나 : 내 자식노드들이 갖고 있는 최소 얼리어답터수의 합

으로 구성되는데 이게 리프노드로 가면 본인밖에 없어서 [0] = 1, [1] = 0 으로 결정됨 -> 재귀로 위로 쭉쭉 올라가면 루트노드의 값이 구해짐

 

과연..이걸 알아들을 수 있을지 나중에

 

소스코드

import Foundation

func solution() -> Int {
    
    let N:Int = Int(readLine()!)!
    var adj:[[Int]] = [[Int]](repeating: [], count: N+1)
    
    for _ in 0..<N-1 {
        let uv:[Int] = (readLine()?.split(separator: " ").map { Int($0)! })!
        adj[uv[0]].append(uv[1])
        adj[uv[1]].append(uv[0])
    }
    
    var dp:[[Int]] = [[Int]](repeating: [0,0], count: N+1)
    var visit:[Bool] = [Bool](repeating: false, count: N+1)
    
    func findMinAdap(_ n:Int) {
        visit[n] = true
        
        // 내가 어답터
        dp[n][0] = 1
        for c in adj[n] {
            if !visit[c] { // 부모노드 판단용
                findMinAdap(c)
                dp[n][0] += min(dp[c][0], dp[c][1])
                dp[n][1] += dp[c][0]
            }
        }
        
    }
    findMinAdap(N) // 루트노드가 어디인지는 상관없음 어디든 루트노드가 될 수 있음
    return min(dp[N][0], dp[N][1])
}

print(solution())