사회망 서비스(SNS)(백준_2533)

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

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

 

문제 설명

• 새로운 아이디어를 먼저 받아들인 사람을 얼리아답터라고 한다.
• 사회망 서비스에 속한 사람은 얼리 아답터 일수도 있고 아닐 수 도 있다.
• 얼리 아답터가 아닌 사람은 자신과 친구 즉 연결되어 있는 사람한테 정보를 받을 수 있다.
• 최소한 수의 얼리 아답터를 확보하여 모든 사람이 아이디어를 받아들이게 하자!!
• 이때, 친구 관계 그래프는 트리이다.

문제의 예시처럼 2,3,4 가 얼리 어답터라면 1,5,6,7,8은 모두 정보를 얻을 수 있다.

 

문제에 대한 설명

이 문제를 제일 처음 봤을 때는 parent를 이용해서 풀어보자라고 생각했다.

왜냐하면 parent가 얼리 아답터인 경우 자신의 자식과 부모는 모두 정보를 얻을 수 있기 때문이다.

• BFS로 자신의 부모 찾기
• 부모의 수 count 
• 만약 부모가 1인 경우는 자신의 자식이 얼리 아답터인지 체크하고 빼준다. 
• 자식 중에 얼리 아답터가 여러명 이면 얼리 아답터가 아니어도 정보 전달이 가능한 경우는 빼줘야 한다. 

결과는 틀렸다 ㅜㅜ

 

문제점 살펴보기

왜 틀렸는지 고민을 해보니 1번이 얼리 아답터인 경우도 존재한다. 최소의 얼리 아답터의 경우의 수가 하나가 아니라는 것이다. 이런 문제는 DP를 사용해야 한다. 점화식을 사용해 모든 가능한 요소들을 조사해 보고 그중 최소를 선택해야 한다,

 

DP를 이용해서 풀기

DP는 언제나 점화식을 잘 짜야 한다!!

여기서는 DP 배열을 얼리 아답터가 아닌 경우와 얼리 아답터인 경우로 생각한다.

예를 들어 dp[][]이런 배열이 있을 때, dp[1][0]은 1이 얼리 아답터가 아닌 경우 dp[1][1]은 얼리 아답터인 경우이다.

그 후 조건을 생각해 본다.

• dp[n][0] : 자신이 얼리 아답터가 아닌 경우는 그 의 자식이 얼리 아답터여야 한다.

dp[parent][0] += dp[child][1]

• dp[n][1] : 자신이 얼리 아답터인 경우는 자식이 얼리 아답터 여도 되고 아니어도 된다.

dp[parent][1] += Math.min(dp[child][0], dp[child][1])

이렇게 점화식을 세워 볼 수 있다.

 

구현

static ArrayList<Integer> ar[]; // 트리를 저장할 ArrayList
static int dp[][]; // dp 배열
static boolean visited[]; // visited 배열

• Main

public static void main(String []args) throws IOException {
    BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(buf.readLine());
    StringTokenizer st;
    ar = new ArrayList[n + 1];
    dp = new int[n+1][2];
    visited = new boolean[n + 1];
    for (int i = 1; i <= n; ++i) {
        ar[i] = new ArrayList<>();
    }
    //트리 만들기
    for (int i = 0; i < n - 1; ++i) {
        st = new StringTokenizer(buf.readLine());
        int u = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
        ar[u].add(v);
        ar[v].add(u);
    }
    DFS(1);
    //둘중 최소를 출력한다.
    System.out.println(Math.min(dp[1][0],dp[1][1]));
}

• DFS

public static void DFS(int start){
    visited[start] = true;
    dp[start][0] = 0; //처음은 0
    dp[start][1] = 1; //처음이 얼리 아답터라면 1
    for(int i =0; i<ar[start].size(); ++i){
        int next = ar[start].get(i); //자식
        if(visited[next]) continue; 
        DFS(next); // 자식으로 먼저 내려가기 즉 리프 노드부터 처리하면서 올라온다.
        dp[start][0] += dp[next][1]; //얼리 아답터인 경우
        dp[start][1] += Math.min(dp[next][0],dp[next][1]); // 얼리 아답터가 아닌 경우
    }
}

https://github.com/Heron-Woong/CodingTest_Practice/commit/d7751ef0caa1db4d42489d721fe41a4846b2b33c

백준_2533, 사회망 서비스(SNS) · Heron-Woong/CodingTest_Practice@d7751ef