🔗
서로 연결된 관계를 친구관계라고 정의한다. 친구 관계는 양방향이며 사이클이 되는 경우는 존재하지 않으므로 트리이다. 다만 양방향이기 때문에 아래와 같이 모든 노드가 루트로 선정될 수 있다.
모든 노드는 2가지 상태를 가질 수 있다.
- 자기 자신이 얼리어답터이다.
- 친구 관계에 있는 모든 노드가 얼리어답터이다.
이때 주의할 점은 친구 관계에 있는 모든 노드 라는 점이다. 모든 노드가 두 가지 상태 중 하나의 값을 가지고 위의 그림처럼 특정 노드를 루트 노드로 하는 트리 구조를 가진다고 가정했을 때, 해당 노드를 루트 노드로 하는 서브 트리가 가지는 최소한의 얼리어답터 개수 정보를 2차원 배열에 저장할 수 있다.
배열의 첫번째 칸에는 자기 자신이 얼리어답터일 때 아래의 서브트리들이 가질 수 있는 최소한의 얼리어답터 개수가, 두번째 칸에는 자기 자신은 얼리어답터가 아니지만 주변의 모든 노드들이 얼리어답터일 때 가질 수 있는 최소한의 얼리어답터 개수가 저장된다.
트리 구조이기 때문에 루트 노드부터 리프 노드까지 타고 내려가서 아래에서부터 위로 올라오는 방식으로 계산된다.
리프 노드부터 계산하면 리프 노드는 아래에 따로 가지는 서브 트리가 없기 때문에 자기 자신이 얼리어답터인 경우 가질 수 있는 최소한의 얼리어답터 개수는 1개이다. 반면에 자기 자신이 얼리어답터가 아닌 경우 어차피 아래에는 노드들이 없기 때문에 최소한의 얼리어답터 노드 개수는 0개이다. 이때 해당 리프 노드의 위쪽으로 연결된 친구 관계에 있는 노드는 반드시 얼리어답터여야 한다.
이제 리프 노드에서 한 칸 올라와서 계산한다. 4를 기준으로 생각하면 아래의 노드가 모두 리프 노드들이고 전부다 [1, 0] 의 값을 가지게 된다. 만약 4가 얼리어답터가 아니라면 아래에 있는 노드들은 모두 반드시 자기 자신이 얼리어답터여야 한다. 즉 [0]번째 인덱스에 있는 값들을 모두 더해서 4의 [1]번 인덱스에 더해줘야 한다.
하지만 만약 4가 얼리어답터라면 아래의 리프 노드들은 굳이 얼리어답터여야 할 필요는 없다. 또한 반드시 얼리어답터가 아닐 필요도 없다. 이미 4가 얼리어답터 이기 때문에 리프 노드의 얼리어답터 여부는 크게 중요하지 않다. 중요한 건 최소값을 구해야 하는 것이므로 둘 중 더 작은 값을 구해서 더해주면 된다.
dp[parent][1] += dp[child][0]
dp[parent][0] += min(dp[child])
서브 트리에는 자기 자신이 반드시 포함되므로 dp[parent][0] 에는 항상 1이 초기화되어야 한다.
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static List<List<Integer>> arr;
static int[][] dp;
static boolean[] visited;
public static void dfs(int parent) {
dp[parent][0] = 1;
visited[parent] = true;
for (int child: arr.get(parent)) {
if (visited[child]) continue;
dfs(child);
dp[parent][0] += Math.min(dp[child][0], dp[child][1]);
dp[parent][1] += dp[child][0];
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
arr = new ArrayList<>(N+1);
dp = new int[N+1][2];
visited = new boolean[N+1];
for (int i = 0; i <= N; i++) {
arr.add(new ArrayList<>());
}
StringTokenizer st;
int u; int v;
for (int i = 0; i < N-1; i++) {
st = new StringTokenizer(br.readLine(), " ");
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
arr.get(u).add(v);
arr.get(v).add(u);
}
dfs(1);
System.out.println(Math.min(dp[1][0], dp[1][1]));
}
}
