백준 2533번 : 사회망 서비스 (SNS) [자바]

 

🧫 문제 분석

 

✔️ 출처

사회망 서비스 (SNS) 골드 3

 

📖 문제

 

 

DP 문제

트리를 이용한 DP 문제는 처음이라 좀 어려웠다

 

처음에는 엣지가 많은 노드 순으로 연결 해제 여부를 따지며 선정하면 되지않나 싶었는데

불가능한 케이스가 있어서 바꿨다.

 

현재 노드를 얼리 아답터로 선정할지 안할지에 대해서 탐색하면된다.

DFS+DP 식으로 풀어서 별로일 수 있다. 

 

또한 입력을 받을 때 주의해야한다.

방향성을 가지면 안되며 양방향으로 트리를 만들어야한다.

그 이유는 단방향시 루트를 가지는 트리가 되는데 이러면 

방향에 따라 값이 달라진다.

 

5
1 5
2 1
2 3
2 4

이런 입력이 들어오면 1을 루트로 설정시

2를 탐색할 수 없다. 때문에 양방향으로 설정해야한다.

 

루트를 1 기준으로 입력이 들어온다는 생각때문에

이런 실수를 했다.

 

양방향 관계로 설정후 아무 노드나 루트노드로 써도된다. 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {

    static List<Integer>[] graph;
    static boolean[] visited;
    static int[][] dp; // [n개의 정점, 얼리 아답터 여부 ]

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        visited = new boolean[n + 1];
        graph = new List[n + 1];
        dp = new int[n + 1][2];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
            Arrays.fill(dp[i], -1);
        }

        for (int i = 1; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            graph[v1].add(v2);
            graph[v2].add(v1);
        }
        graph[0].add(1);
        System.out.println(dfs(0, 1));

    }


    // 켜져있을 시 , 자식노드는 키거나 끌 수 있음
    // 꺼져있을 시 , 자식노드는 무조건 켜야함
    private static int dfs(int node, int onOff) {
        if (graph[node].isEmpty()) {
            return 0;
        }

        if (dp[node][onOff] != -1) {
            return dp[node][onOff];
        }

        dp[node][onOff] = 0;
        for (int next : graph[node]) {
            if (!visited[next]) {
                visited[next] = true;

                // 부모가 켜져있을 경우
                if (onOff == 1) {
                    dp[node][onOff] += Math.min(dfs(next, 0), 1 + dfs(next, 1));

                    // 부모가 꺼졌을 경우
                } else {
                    dp[node][onOff] +=  1 + dfs(next, 1);
                }
                visited[next] = false;
            }
        }

        return dp[node][onOff];
    }
}

 

🔅 다른 사람 풀이 이해해보기

private static void dfs(int node) {
    dp[node][1] = 1;
    for (int next : graph[node]) {
        if (!visited[next]) {
            visited[next] = true;
            dfs(next);

            dp[node][0] += dp[next][1];
            dp[node][1] += Math.min(dp[next][0], dp[next][1]);

        }
    }
}

 

사실상 현재 노드를 얼리 어답터로 선정할 경우 자식 노드는 선정하든지 안하든지 둘 중 하나의 값을 가지며 이중 최솟값을 가지면 되고

현재 노드가 얼리 아답터가 아닐 경우 자식 노드는 무조건 얼리 아답터로 선정해야하기에 위와 같은 알고리즘이 가능하다.

 

❗ 오답노트 / 필요한 지식

1. 양방향 캐치 못한게 많이 아쉽다. 그래프는 항상 방향성을 생각해야한다.