[백준_1949번] 우수 마을

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

1949번: 우수 마을

[문제]

 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다.

 이 나라의 주민들에게 성취감을 높여 주기 위해, 다음 세 가지 조건을 만족하면서 N개의 마을 중 몇 개의 마을을 '우수 마을'로 선정하려고 한다.

 

1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

 각 마을 주민 수와 마을 사이의 길에 대한 정보가 주어졌을 때, 주어진 조건을 만족하도록 '우수 마을'을 선정하는 프로그램을 작성하시오.

 

[입력 조건]

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 이하이다. 셋째 줄부터 N-1개 줄에 걸쳐서 인접한 두 마을의 번호가 빈칸을 사이에 두고 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_1949 {
	static int n;
	static int[] people;
	static int[][] dp;
	static ArrayList<ArrayList<Integer>> graph=new ArrayList<>();

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		people=new int[n+1];
		
		/*
		 * dp[n][0] : n번 마을이 우수 마을이 아닐때, n번 마을을 루트노드로 하는 하위트리의 마을 주민 수
		 * dp[n][1] : n번 마을이 우수 마을일 때, n번 마을을 루트노드로 하는 하위트리의 마을 주민 수
		 */
		dp=new int[n+1][2];
		
		for(int i=0;i<=n;i++)
			graph.add(new ArrayList<>());
		
		for(int i=1;i<=n;i++)
			people[i]=sc.nextInt();
		
		for(int i=0;i<n-1;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			// 양방향
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		
		dfs(1,0);
		System.out.println(Math.max(dp[1][0],dp[1][1]));
	}
	
	static void dfs(int now, int parent) {
		for(int child:graph.get(now)) {
			if(child!=parent) {
				dfs(child,now); // dfs를 수행하면서 맨 아래에 도달해 트리의 아래에서 위로 올라오면서 dp 값을 구한다
				dp[now][1]+=dp[child][0]; // now 노드가 우수마을로 선정되면 자식 노드는 우수마을로 선정될 수 없다.
				/*
				 * now 노드가 우수마을로 선정되지 않았을 경우 자식 노드중 몇 개의 노드가 우수마을이 되도 상관 없다.
				 * 자신의 자식 노드를 모두 탐색하면서 두 가지의 경우 중 큰 값의 누적 합을 구한다. 
				 */
				dp[now][0]+=Math.max(dp[child][0],dp[child][1]);
				
			}
		}
		/*
		 * dfs를 수행하다 트리의 맨 아래에 도달하면 해당 노드는 자식노드가 없기 때문에 
		 * 우수마을로 선정될 경우만 자신의 인구 수를 저장하고, 우수마을로 선정되지 못한다면 기존 값 0을 가져간다.
		 */
		dp[now][1]+=people[now];
	}
}

 

[고찰]

 이번 문제는 트리 구조로 구성되어 있는 데이터를 DFS와 DP 알고리즘으로 탐색하여 마을 인원 수가 최대가 되도록 우수마을을 선정하는 문제이다. DFS 알고리즘으로 루트 노드에서부터 리프 노드까지 내려간 수 위로 올라오면서 dp 배열을 갱신해야 한다. dp 배열은 해당 노드가 우수 마을로 선정됐는가의 여부에 따라 인구의 최댓값을 따로 구해야 하기 때문에 2차원의 배열로 이루어져야 한다.

• dp[n][0] : n번 마을이 우수 마을이 아닐 때, n번 마을을 루트노드로 하는 하위트리의 마을 주민 수의 총합
• dp[n][1] : n번 마을이 우수 마을일 때, n번 마을을 루트노드로 하는 하위트리의 마을 주민 수의 총합

 

 만약 n번째 마을이 우수 마을로 선정됐을 경우 n번째 노드의 자식 노드는 모두 우수 마을이어서는 안된다. 반면에 n번째 마을이 우수 마을로 선정되지 않았을 경우 자식 노드는 모두 우수 마을이 될 수 있고 그 중 한개만 우수 마을일 수 있다. 따라서 자식 노드를 모두 탐색하면서 자식 노드가 우수 마을일 경우와 우수 마을이 아닐 경우 중 큰 값을 선택해 누적해 주면 된다. 

• dp[n][0] = Math.max(dp[자식노드1][0], dp[자식노드1][1]) + Math.max(dp[자식노드2][0], dp[자식노드2][1]) ...
• dp[n][1] = dp[자식노드1][0] + dp[자식노드2][0] + ... + dp[자식노드m][0]

 

이렇게 맨 아래의 리프 노드부터 탐색해가며 루트 노드까지 도달했을 때 루트 노드가 우수 마을로 선정됐을 경우와 그렇지 않은 경우 중 큰 값이 정답이 된다. 

 

트리 자료구조에 DFS와 DP 알고리즘을 동시에 접목시키는 문제는 많이 풀어보지 않아 다른 사람의 풀이를 여러개 읽어보면서 이해하였다. DP는 평소에도 어려워하는 알고리즘 중 하나라 좀 더 난이도가 높게 느껴졌던 것 같다. 다음에 다시 한번 풀어봐야겠다.