백준 1949번 우수 마을 (JAVA)

백준 1949번 우수 마을 (JAVA)

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

트리에서 루트가 정해져 있지 않다는 점을 이용한 DP 문제이다.

가장 처음에 이런 유형의 문제를 풀 때 루트가 정해진 트리로 접근했다가 틀렸던 기억이 있다. 비슷한 문제로 사회망 서비스 SNS 문제가 있다.

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

DP 문제를 풀때는 결국 문제를 작게 쪼개려고 노력해야 한다고 생각한다.

이 문제의 경우에는 루트 노드로 정한 마을이 우수 마을로 선택되는가 / 선택되지 않는 가의 두가지 경우에 따라서 답이 달라지고, 그것을 DP의 형태로 풀어서 문제를 해결하면 된다.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; import java.util.function.Function; public class Main { static int[][] dp; static int[] popul; static int N; static ArrayList[] roads; static Function stoi = Integer::parseInt; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = stoi.apply(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()); popul = new int[N + 1]; dp = new int[N + 1][2]; // 0 -> 1번 노드 선택 O 1 -> 1번 노드 선택 X roads = new ArrayList[N + 1]; for (int i = 1; i <= N; i++) { popul[i] = stoi.apply(st.nextToken()); roads[i] = new ArrayList(); } for (int i = 0; i < N - 1; i++) { st = new StringTokenizer(br.readLine()); int s = stoi.apply(st.nextToken()); int e = stoi.apply(st.nextToken()); roads[s].add(e); roads[e].add(s); } dfs(1, 0); System.out.println(Math.max(dp[1][0], dp[1][1])); } private static void dfs(int now, int parent) { for (int road : roads[now]) { if (road != parent) { dfs(road, now); dp[now][0] += Math.max(dp[road][0], dp[road][1]); dp[now][1] += dp[road][0]; } } dp[now][1] += popul[now]; } }

특정 노드를 루트 노드로 정하면 우리가 아는 트리의 형태로 트리를 재배열할 수가 있다.

이후 부모 노드로 거슬러올라가지않으며(road != parent)

dfs를 반복하면 된다.

dp[now][0]인 경우는 현재 마을이 우수마을이 아닌 경우이며, 이 경우에는 내 자식이 우수마을인 경우도, 아닌 경우도 있을 수 있다.

dp[now][1]인 경우는 현재 마을이 우수마을인 경우이며, 이 경우에 내 자식 마을은 모두 우수마을이 아니어야만 한다.

from http://wnwngus.tistory.com/54 by ccl(A) rewrite - 2021-08-08 15:26:20