[백준] 2533. 사회망 서비스(Java)

문제

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

 

풀이

주어진 간선을 활용해 그래프를 형성하고 최소 얼리어답터 수를 구하기 위해 dp를 이용하는 문제입니다.

 

1. 입력 간선을 바탕으로 무방향 그래프를 형성할 때

노드별 진입차수를 저장하는 배열을 만들어 놓습니다.

이를 이용해서 진입차수가 0인 노드를 루트노드로 지정합니다.

(해당 문제에서는 루트노드가 1번이라고 나와있진 않지만, 1번이 루트노드로 두어도 정답이긴합니다만 직접 구해보았습니다.)

 

2. dp는 2차원 배열로 생성합니다.

dp[해당 노드][해당 노드가 얼리라면 1, 아니라면 0] = 총 얼리 수(최소)를 저장합니다.

 

3. 재귀를 돌면서 dp에 값을 저장해 둡니다.

현재노드가 얼리라면 얼리가 1개인 것이고, [현재노드][1] = 1;

여기서 현재노드에서 갈 수 있는 다음 노드가 있다면 다음 노드를 진행해줍니다.

 

재귀함수를 빠져나왔을 타이밍에는 dp값이 갱신되어 있을 것이며

현재노드가 얼리가 아니라면, 다음 노드는 반드시 얼리노드여야 하기 때문에

dp[현재노드][0] += dp[다음노드][1];

현재노드가 얼리라면, 다음 노드는 얼리노드일수도 아닐수도 있기 때문에

그중 작은 값을 더해줍니다.

dp[현재노드][1] += Math.min(dp[다음노드][1], dp[다음노드][0]);

 

4. 재귀를 마치고나서

루트노드가 얼리일 경우와 얼리가 아닐경우 중 최솟값이

문제에서 원하는 얼리의 최소개수가 되며 리턴하면 끝

 

코드

429,628 KB / 2392 ms / 1771 B

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

public class Main {
    static int N;
    static int[][] dp;
    static List<Integer>[] list;
    static int[] in;
    static boolean[] v;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        in = new int[N+1];
        dp = new int[N+1][2];
        list = new ArrayList[N+1];
        v = new boolean[N+1];

        for(int i = 1 ; 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());

            in[b] ++;
            list[a].add(b);
            list[b].add(a);
        }

        int root = 0;
        for(int i = 1 ; i <= N ; i ++)
            if(in[i] == 0){
                root = i;
                break;
            }

        recur(root, 0);

        // root노드가 얼리일때와 아닐때 중 작은 값 출력
        System.out.println(Math.min(dp[root][0], dp[root][1]));
    }

    private static void recur(int cur, int prev) {
        // 현재노드가 얼리라면
        dp[cur][1] = 1;

        for(int next: list[cur]){
            if(next == prev) continue;

            recur(next, cur);

            // 현재노드가 얼리가 아니면, 다음은 반드시 얼리여야 함
            dp[cur][0] += dp[next][1];
            // 현재노드가 얼리라면, 다음 노드는 얼리거나 얼리가 아닌데 그 중 최솟값을 더해줌
            dp[cur][1] += Math.min(dp[next][0], dp[next][1]);
        }
    }
}