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

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

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

 

문제 해석

얼리 어답터는 어떤 소식을 가장 먼저 알게 됩니다.

 

주변에 연결되어 있는 친구들끼리만 해당 소식을 전파할 수 있습니다.

 

모든 정점 사이에 이들을 잇는 경로가 존재하고 사이클이 존재하지 않는다고 고려합니다.

 

모든 개인이 새로운 소식을 받기 위한 최소 얼리 어답터의 수를 구하세요

 

N은 최대 백만 개입니다.

문제 풀이 전 설계

이분 탐색을 활용한 파라미터 서치?

 

문제 풀이

자신이 얼리어답터인지, 아닌지 2가지의 경우로 나누어 얻을 수 있는 최솟값을 구해야 합니다.

 

1. 자신이 얼리어답터가 아니라면, 인접 노드들은 모두 얼리어답터여야 한다. (그래야 어떻게든 아이디어 전파가 가능)

 

2. 자신이 얼리어답터라면, 인접 노드들은 얼리어답터일 수도 있고, 아닐 수도 있다.

 

이를 위해 인접 리스트를 통해 정점들을 표현해주었다.

 

그리고 1을 루트로 가정하고, 1이 얼리어답터인지 아닌지 2가지의 경우로 나누어 확인하며, DFS를 통해 단말 노드까지 내려가게 된다.

 

dp[cur][0] = 0; // cur 현재 노드가 얼리어답터가 아닌 경우 0

dp[cur][1] = 1; // cur현재 노드가 얼리어답터인 경우 1

 

코드

import java.util.LinkedList;
import java.util.Scanner;

public class Main_2533_사회망서비스SNS {
    public static LinkedList<Integer>[] adjList;
    public static boolean[] visited;
    public static int[][] dp;
    public static int N;
    public static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        adjList = new LinkedList[N+1];
        visited = new boolean[N+1];
        dp = new int[N+1][2];

        // 정점 N개의 인접 리스트 생성
        for (int i = 1; i <= N; i++) {
            adjList[i] = new LinkedList<Integer>();
        }

        for(int i = 0; i < N-1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            adjList[a].add(b);
            adjList[b].add(a);
        }

        dfs(1); // 1을 루트로 가정해 1부터 시작
        System.out.println(Math.min(dp[1][0], dp[1][1]));

    }

    public static void dfs(int cur) {
        //현재 정점이 얼리어답터가 아닌 경우 0
        // -> 인접 노드는 얼리어답터여야지 아이디어를 전파할 수 있음
        dp[cur][0] = 0;

        // 얼리어답터인 경우 1
        // -> 인접 노드는 얼리어답터이거나 아닐 수도 있음, 즉 둘을 dfs로 파악 후 더 작은 값으로 초기화
        dp[cur][1] = 1;
        visited[cur] = true;

        LinkedList<Integer> list = adjList[cur];

        for(int i = 0; i < list.size(); i++) {
            // DFS 무한 루프와 이전에 간 곳 다시 가지 않기 위해, 아직 방문하지 않은 인접 정점인 경우만 DFS
            if(!visited[list.get(i)]) {
                dfs(list.get(i)); // 인접 정점을 시작으로 다시 dfs
                //만약 해당 노드가 얼리어답터가 아니면 자식노드는 얼리어답터여야 함
                dp[cur][0] += dp[list.get(i)][1];
                // 인접 노드가 얼리어답터인지 아닌지 판단 후 더 작은 값으로 초기화
                //해당 노드가 얼리어답터라면 자식노드는 얼리어탑터여도 되고 아니여도 됨
                dp[cur][1] += Math.min(dp[list.get(i)][0], dp[list.get(i)][1]);
            }
        }
    }

   

}

 

 

 

 

 

출처

https://maivve.tistory.com/322

(JAVA) 백준 2533번 : 사회망 서비스(SNS) -- [DP, DFS]