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

문제

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

2533번: 사회망 서비스(SNS)

N명의 친구들이 서로 트리 형태로 연결되어있다.

친구들은 자신의 친구들이 모두 얼리어답터 일때, 자신도 얼리어답터가 된다.

 

이때, 모든 친구를 얼리어답터를 만들기위해 필요한 초기 얼리어답터 수를 구하는 문제다.

---

풀이

다이나믹 프로그래밍으로 푼 문제다.

트리에서의 DP의 전형적인? 유형으로 DP로 풀리는것을 떠올리는것이 문제였다.

 

아이디어

트리의 현재 노드에 할수있는 연산은 두 가지다. 

1. 현재 노드를 얼리어답터로 만든다.

2. 현재 노드를 얼리어답터로 만들지 않는다.

 

1번 연산의 경우, 현재 노드가 얼리어답터니 자신의 자식 노드들은 각각 얼리어답터여도 되고 아니여도 된다. 즉, 자식 노드 각각을 "얼리어답터로 만드는경우" 와 "얼리어답터로 만들지 않는 경우"중 얼리어답터의 수가 최솟값이 되는 경우를 선택해서 가져온다. 

 

2번 연산의 경우, 현재노드가 얼리어답터가 아니므로, 자신의 자식 노드들은 전부 얼리어답터가 되어야 한다. 따라서, 자신의 자식 노드들을 전부 "얼리어답터로 만드는경우" 얼리어답터의 수를 가져온다.

 

구현

위 아이디어를 그대로 구현했다.

각 노드별로 두가지상태(얼리어답터 O, X)를 표현해야하므로 2차원 DP를 만들었다.

- dp[node][2] = 현재 상태의 최소 얼리어답터 수

 

1번을 항상 루트노드로 잡고, 자식들을 훑으며 최솟값을 찾아준다.

 

주요 소스코드

private int getEarlyAdopterCount(int idx){
    visit[idx] = true;
    for(int i = 0; i < graph.get(idx).size(); i++){
        int son = graph.get(idx).get(i);
        if(visit[son]) continue;
        dp[idx][1] += getEarlyAdopterCount(son);
        dp[idx][0] += dp[son][1];
    }
    dp[idx][1]++;
    return min(dp[idx][1], dp[idx][0]);
}

 

모든 노드들을 한번씩 반복하므로 시간복잡도는 O(N)이 된다.

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/2533%20%EC%82%AC%ED%9A%8C%EB%A7%9D%20%EC%84%9C%EB%B9%84%EC%8A%A4(SNS)/Main.java 

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃