[Java] BaekJoon 2533. 사회망 서비스(골드3) (DFS, DP)

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

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

 

문제이해

목표

N개의 친구관계로 이루어진 그래프 (1~N)
이 그래프는 최소 스패닝 트리(MST)로 모두 양방향 연결되어 있다.
조건: 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다. 

이를 만족하면서 모든 개인이 새로운 아이디어를 수용할 수 있도록 필요한 최소 얼리어답터의 수 도출하여라

 

풀이

연결된 상태를 나태내는 인접리스트(adjList),

필요한 최소 얼리어답터의 수를 저장할 배열(dp[][])를 만든다.

 

dp의 정보는 다음과 같다.

dp[현재친구 번호][현재친구 얼리어답터 여부]  

 dfs로 탐색을 진행 할 건데, 조건을 먼저 확인해 보자.

 

먼저 우선적으로 

dp[now][1] = 1   => 현재 친구가 얼리어답터이기 때문에 얼리어답터 수 1로 초기화해준다.

dp[now][0] = 0   => 현재 친구가 얼리어답터가 아니기 때문에 얼리어답터 수 0으로 초기화해준다.

 

조건1에 따라, 

• dp[now][0] 인경우 연결된 친구들이 모두 얼리어답터여야 한다. 
  dp[now][0] += for ( sum(dp[next][1]) )
• dp[now][1] 인 경우 연결된 친구들이 얼리어답터여도 되고 아니어도 되기 때문에, 둘중 작은 값을 + 해준다.
  dp[now][1] += for ( Min(dp[next][0], dp[next][1]); )
  
  

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class 사회망서비스 {
    private static int N;
    private static int[][] dp;
    private static ArrayList<Integer>[] adjList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 본인이 얼리어답터이다. dp[][1]  => 주변친구가 얼리어답터이거나 아니다. 둘중에 더 작은값 채택
        // 본인이 얼리어답터가 아니다. dp[][0] => 주변모든 친구가 얼리어답터이다.
        N = Integer.parseInt(br.readLine());
        String[] strArr;
        dp = new int[N+1][2];
        // 인접리스트 만들기
        adjList = new ArrayList[N + 1];
        for (int i = 1; i <= N ; i++) {
            adjList[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            strArr = br.readLine().split(" ");
            int num1 = Integer.parseInt(strArr[0]);
            int num2 = Integer.parseInt(strArr[1]);
            adjList[num1].add(num2);
            adjList[num2].add(num1);
        }

        // 1부터 시작하여 최소 얼리어답터를 구하는 dfs구현
        getMinAdapter(1, 0);
        int answer = Math.min(dp[1][0], dp[1][1]);
        System.out.println(answer);
    }

    private static void getMinAdapter(int now, int parent) {
        dp[now][0] = 0;
        dp[now][1] = 1;

        for (Integer next : adjList[now]) {
            if(parent == next){
                continue;
            }
            getMinAdapter(next, now);
            dp[now][0] += dp[next][1];
            dp[now][1] += Math.min(dp[next][0], dp[next][1]);
        }
    }
}