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

문제 링크

문제 정의

• 사회망 서비스에 속한 사람들은 '얼리 아답터'이거나 '얼리 아답터가 아닌 사람'로 구분
• '얼리 아답터가 아닌 사람`들은 자신의 모든 친구들이 얼리 아답터일 때만 아이디어를 수용
• 친구 관계 트리가 주어졌을 때
  모든 개인이 새로운 아이디어를 수용하기 위하여 필요한 최소 얼리 어답터의 수 구하기

---

접근 방법

이 문제는 트리 구조이며 정점의 수 $N$은 $1,000,000$이기 때문에
최대 $O(NlogN)$의 시간 복잡도 내에 문제를 풀도록 구현해야 합니다.

여기에 각 정점은 두 가지 상태를 가질 수 있습니다.

• 자신이 얼리 어답터인 상태
• 자신이 얼리 어답터가 아닌 상태

그리고 트리의 리프 노드는
'자신이 얼리 어답터인 상태'에서는 1의 값
'자신이 얼리 어답터가 아닌 상태'에서는 0의 값을 가지고 있습니다.

이 정보들을 활용해서 문제를 풀도록 해야 하는데
생각해낸 방안은 DFS와 DP였습니다.

---

DFS

트리에서 DFS는
현재 정점에서 자식 노드들을 모두 탐색하고
필요한 연산을 수행 후
현재 정점의 부모 노드로 돌아갈 수 있습니다.

이 매커니즘을 활용해서
먼저 리프 노드부터 탐색 후 리프 노드의 값을 활용해
그 부모의 노드에서의 값을 계산할 수 있게 되고
연쇄적으로 최상위 노드까지 계산이 가능하게 됩니다.

---

DP

그러면 이번 문제에서는 어떤 값을 저장해야할까요?

DFS는 내 자식들을 모두 탐색하고 올라오는 매커니즘이라고 했는데
리프 노드부터 bottom-up으로 수행됩니다.

그렇기 때문에 나와 연결된 리프 노드부터 현재 노드까지
얼리 어댑터가 최소가 되는 값을 메모이제이션하면 될 것 같다고 생각했습니다.

그러면 이전에 제가 현재 정점은 두 가지 상태가 될 수 있다고 했는데
이 두 가지 상태를 기억하도록 2차원 배열의 DP를 생성하면 될 것 같습니다.
그리고 dp 배열의 의미는 아래와 같습니다.

---

Case 1: 내가 일반인일 때 (dp[v][0])

내가 얼리 어답터가 아니므로
나를 커버해주기 위해 나의 모든 자식 노드(nv)들은 반드시 얼리 어답터여야만 합니다.

$dp[v][0] = Σ (dp[nv][1])$

Case 2: 내가 얼리 어답터일 때 (dp[v][1])

내가 이미 얼리 어답터이므로자식들은 일반인이든 얼리 어답터이든 상관없습니다.
따라서 자식들의 상태 중 더 인원수가 적은 쪽을 선택합니다. (본인 포함 +1)

$dp[v][1] = 1 + Σ(min(dp[nv][0], dp[nv][1]))$

---

최종 로직

• 초기화 (dp배열, 연결된 노드 배열 graph)
• DfS 수행 (파라미터로 현재 정점과 부모 정점)
  • 자식 노드들은 DFS수행 후 현재 정점의 dp[v]값 갱신 로직 수행
• 정답 출력

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Node {
	int v;
	Node node;

	public Node (int v, Node node) {
		this.v = v;
		this.node = node;
	}
}

public class Main {
	static StringTokenizer st;
	static Node[] graph;
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		init();
		dfs(1, -1);
		System.out.println(Math.min(dp[1][0], dp[1][1]));
	}

	static void dfs(int v, int p) {
		dp[v][0] = 0;
		dp[v][1] = 1;

		for (Node node = graph[v]; node != null; node = node.node) {
			int nv = node.v;
			if (nv != p) {
				dfs(nv, v);
				dp[v][0] += dp[nv][1];
				dp[v][1] += Math.min(dp[nv][0], dp[nv][1]);
			}
		}
	}


	static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		dp = new int[N+1][2];
		graph = new Node[N+1];

		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] = new Node(v, graph[u]);
			graph[v] = new Node(u, graph[v]);
		}
	}
}