[BOJ]2533 - 사회망 서비스(SNS) (G3)

suhyun·2023년 3월 1일
0

백준/프로그래머스

목록 보기
81/81

문제 링크

2533-사회망 서비스(SNS)


입력

첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다.
두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에지 (u, v)를 나타내는 두 정수 u와 v가 하나의 빈칸을 사이에 두고 주어진다.

출력

주어진 친구 관계 그래프에서 아이디어를 전파하는데 필요한 얼리 아답터의 최소 수를 하나의 정수로 출력한다.


문제 풀이

처음에는 트리에서 깊이별로 확인해서
하나걸러 하나씩 얼리 어답터면 되겠다라고 생각했지만 그렇게되면 아래와 같은 반례가 발생한다.

그렇다면? 아래 조건을 만족시키면 된다

부모가 얼리어답터라면? 자식은 얼리어답터가 아니어도 ok
부모가 얼리 어답터가 아니라면? 자식은 무조건 얼리 어답터야함

dp를 2차원 배열로 만들어서 확인한다.

dp[i][0] - i번째 노드가 얼리 어답터인 경우
dp[i][1] - i번째 노드가 얼리 어답터가 아닌 경우

얼리 어답터인 경우에는 현재 노드와 연결된 모든 노드가 얼리 어답터여야하기때문에 연결된 노드들의 갯수 추가
얼리 어답터가 아닌 경우에는 연결된 노드들의 상태가 상관이 없기 때문에,
연결된 노드가 얼리 어답터인 경우와 아닌 경우 중 최소값으로 저장

package Algorithm;

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

public class Main {
    static int n;
    static int[][] dp;
    static ArrayList<Integer>[]list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());

        dp = new int[n + 1][2];
        list = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }
        DP(1, -1);  // 트리구조이기때문에 1부터 시작
        System.out.println(Math.min(dp[1][0], dp[1][1]));
    }

    public static void DP(int cur, int parent) {
        dp[cur][0] = 0; // 현재노드가 얼리어답터가 아닌경우
        dp[cur][1] = 1; // 현재노드가 얼리어답터인 경우

        for (int next : list[cur]) {
            if (next != parent) {
                DP(next, cur);
                dp[cur][0] += dp[next][1];
                dp[cur][1] += Math.min(dp[next][0], dp[next][1]);
            }
        }
    }
}
profile
꾸준히 하려고 노력하는 편 💻

0개의 댓글