[백준] 2533 사회망 서비스(SNS) - 트리(Tree) + DP JAVA

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

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

코드설명

트리와 DP를 활용하여 진행합니다.

 

문제에서 트리의 형태로 입력이 주어진다고 합니다.

그것에 맞추어서 양방향 그래프를 만들어줍니다. 문제에서 입력순서가 트리의 순서가 아니니 양방향 그래프입니다.

 

문제의 로직은, 

1. 부모노드가 얼리어답터가 아니라면, 자식노드는 얼리어답터여야만 합니다.

2. 부모노드가 얼리어답터라면, 자식노드는 얼리어답터여야만 합니다.

 

위의 로직을 활용하여 DFS로 Child의 얼리어답터 여부를 검사하여 DP 배열을 갱신하면됩니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M;
	public static int[][] map;
	public static boolean[] visited;
	public static int[][] dp; // [nodeIdx][2]  : nodeIdx 노드 번호일때 [0]은 해당 nodeIdx가 얼리어답터일가 아닌경우, [1]은 얼리어답터인경우 
	public static int answer = 0;
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
 
    	N = Integer.parseInt(st.nextToken());
    	visited = new boolean[N+1];
    	dp = new int[N+1][2];
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Integer>());
    	}
    	
    	for(int i=0; i<N-1;i++) {
    		st = new StringTokenizer(br.readLine());
    		int u = Integer.parseInt(st.nextToken());
    		int v = Integer.parseInt(st.nextToken());
    		
    		graph.get(u).add(v);
    		graph.get(v).add(u);
    	}
    	
    	dfs(1); //트리 구조이기에 루트노드인 1 부터 시작합니다.
    	System.out.println(Math.min(dp[1][0], dp[1][1]));
	}
	
	public static void dfs(int start) {
		visited[start] = true;
		dp[start][0] = 0; //해당 number가 얼리어답터가 아닌경우
		dp[start][1] = 1; //해당 number가 얼리어답터인 경우(우선 시작 시 해당 지점 얼리어답터이므로 개수 1)
		
		for(int i=0;i<graph.get(start).size();i++) {
			int temp = graph.get(start).get(i);
			if(visited[temp] == false) { //Child Tree에 아직 방문하지 않았다면, 
				dfs(temp); //Child Tree로 들어가봅니다.
				dp[start][0] += dp[temp][1];
				dp[start][1] += Math.min(dp[temp][1], dp[temp][0]);
			}
		}
	}
	
}