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

 

문제

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

 

알고리즘

트리, 다이나믹 프로그래밍(DP)

 

 

풀이

트리 DP 유형 문제이다.

단말 노드부터 거슬러 올라가며 dp 배열에 저장된 자식 노드의 최솟값을 이용하여 

해당 노드 번호에 해당하는 사람이 얼리어답터일 경우와 아닐 경우의 최솟값을 구하고 저장한다.

 

 

2차원 배열 dp[N+1][2] 를 선언하고

i번째 번호에 해당하는 사람이 얼리어답터가 아닐 경우의 최솟값를 dp[i][0], 맞을 경우의 최솟값을 dp[i][1]에 저장한다.

자신이 얼리어답터가 아닐 경우 자식은 반드시 얼리어답터이어야하고,

자신이 얼리어답터일 경우 자식은 어느 것이든 상관없으므로 자식이 얼리어답터인 경우와 아닌 경우 중 최솟값을 더한다.

 

모든 탐색을 마친 후 처음 탐색을 시작한 노드가 얼리어답터인 경우, 아닌 경우의 최솟값 중 더 작은 값을 출력한다.

static void dfs(int index) {

	visited[index] = true;
	dp[index][0] = 0;
	dp[index][1] = 1;

	for (int child : graph[index]) {
		if(visited[child]) continue;
		dfs(child);
		dp[index][0] += dp[child][1];
		dp[index][1] += Math.min(dp[child][0], dp[child][1]);
	}
}

 

* 양방향 그래프로 만들었기 때문에 방문처리를 하지 않으면 무한 루프에 빠진다.

 

코드

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

public class Main {
	static ArrayList<Integer>[] graph;
	static int[][] dp;
	static boolean[] visited;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		
		dp = new int[N + 1][2];
		visited = new boolean[N + 1];
		graph = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++)
			graph[i] = new ArrayList<>();

		
		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[u].add(v);
			graph[v].add(u);
		}

		dfs(1);
		System.out.println(Math.min(dp[1][0], dp[1][1]));
	}

	static void dfs(int index) {

		visited[index] = true;
		dp[index][0] = 0;
		dp[index][1] = 1;

		for (int child : graph[index]) {
			if(visited[child]) continue;
			dfs(child);
			dp[index][0] += dp[child][1];
			dp[index][1] += Math.min(dp[child][0], dp[child][1]);
		}
	}
}