📝 문제
💡 풀이 과정
⛓ 사용한 알고리즘: dfs, dp
유사한 문제로는 백준의 스티커가 있다. 한 사람이 얼리 어답터일 경우와 그렇지 않은 경우를 따져가며 풀어야 하기 때문에 DP를 이용해서 풀 수 있다! 다만 각 요소들이 트리구조를 가진다는 점에 유의해서 풀이를 진행하면 될 것 같다.
DP 배열을 만들기 위해 문제의 조건을 정리해보자. 우선 하나의 노드가 가질 수 있는 상태는 다음 두 가지가 있다.
- 얼리 어답터인 경우
- 이 경우 스스로가 정보를 확보할 수 있으므로 인접한 노드의 상태는 무엇이 되어도 상관 없다.
- 얼리 어답터가 아닌 경우
- 이 경우에는 인접한 노드 중 하나는 무조건 얼리어답터여야 한다.
- 이 경우에는 인접한 노드 중 하나는 무조건 얼리어답터여야 한다.
1부터 N까지의 노드들이 모두 트리 구조로 되어 있으므로, 위 상태를 바탕으로 각 노드 간의 관계는 다음과 같이 정리할 수 있다.
- 노드 n이 얼리 어답터가 아닌 경우
- 최소 1개 이상의 자식 노드가 반드시 얼리 어답터가 되어야 한다.
- 노드 n이 얼리 어답터인 경우
- 자식 노드들의 상태는 상관없다.
- 자식 노드들의 상태는 상관없다.
이를 dp 배열로 나타내면 dp[N+1][2] 를 활용해서 나타낼 수 있다. 배열의 열 번호는 1~N 노드가 되고, 행은 각각 해당 노드의 상태를 나타낸다. 즉, dp[1][0] 은 1번 노드가 얼리 어답터가 아닐 때를, dp[1][1] 은 1번 노드가 얼리 어답터인 경우를 의미하게 되는것이다.
문제에서 최소 얼리 어답터의 수를 구하라고 했기 때문에, dp 배열에 저장하는 값은 얼리 어답터의 최소 수가 된다. 예를 들어 dp[1][0] 은 1번 노드가 얼리 어답터가 아닌 경우에 최소 얼리 어답터의 수가 저장되는 것이다.
다만 dp배열에 값을 저장할 때 일반적인 방법처럼 순차 탐색으로는 값을 채울 수 없다. 각 노드가 트리 형태로 연결되어 있기 때문이다. 따라서 dfs 탐색을 통해 현재 노드의 자식노드를 탐색하며 dp 배열을 채워야 한다.
우선 dfs 탐색의 대상이 되는 노드를 n이라고 할 때, dp[n][0] 은 0으로, dp[n][1] 은 1로 초기화한다(노드 n이 얼리어답터라고 가정하면 일단 얼리어답터의 수에 본인이 포함되기 때문). 이 때 노드 n의 자식 노드를 a,b 라고 했을 때, 위에서 찾은 노드 간의 관계를 점화식으로 나타내면 다음과 같다.
- 노드 n이 얼리 어답터가 아닌 경우
-
연결된 노드가 무조건 얼리 어답터가 되어야 한다.
dp[n][0] = dp[a][1] + dp[b][1];
-
- 노드 n이 얼리 어답터인 경우
-
이미 본인이 얼리 어답터이므로, 연결된 노드의 상태는 상관 없다. 때문에 그냥 최솟값인 경우를 선택하면 된다.
dp[n][1] = Math.min(dp[a][0], dp[a][1]) + Math.min(dp[b][0], dp[b][1]);
-
위 계산을 n의 모든 자식 노드에 대해서 하고, 자식 노드를 기준으로 두고 재귀적으로 dfs 탐색을 진행하면 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int N;
static List<Integer>[] map;
static boolean[] visit;
static int[][] dp;
static void dfs(int tmp) {
visit[tmp] = true;
//초기값 세팅. 얼리어답터가 아니라면 일단 0이고, 내가 얼리어답터면 얼리어답터 수 1 증가
dp[tmp][0] = 0;
dp[tmp][1] = 1;
for(int next: map[tmp]) { //모든 자식노드 방문
if(visit[next]) continue;
dfs(next);
dp[tmp][0] += dp[next][1];
dp[tmp][1] += Math.min(dp[next][0], dp[next][1]);
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
dp = new int[N+1][2];
map = new ArrayList[N+1];
for(int i=1;i<=N;i++)
map[i] = new ArrayList<>();
StringTokenizer st;
for(int i=1;i<N;i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
map[s].add(e);
map[e].add(s);
}
visit = new boolean[N+1];
dfs(1); //1번노드부터 탐색 시작
System.out.println(Math.min(dp[1][0], dp[1][1]));
}
}