백준 1949번: 우수 마을

문제 설명

• https://www.acmicpc.net/problem/1949
• 하나의 노드가 선택되면 그 인접한 노드는 선택될 수 없습니다.
  하나의 노드가 선택되면 선택된 노드를 포함한 인접한 노드는 효과를 받게 됩니다.
  모든 노드가 효과를 받으면서 노드 값의 합이 최대가 되도록 만들어야 합니다.

접근법

• 문제에서 주어진 입력을 그림으로 표현하면 다음과 같습니다.
  

  • 1,3,5,7을 선택했을 때 최댓값 14000을 얻을 수 있습니다.

• 처음에는 2533번: 사회망 서비스(SNS)문제처럼 i번째를 선택하면 i+1번째를 선택하지 않고, i번째를 선택하지 않으면 i+1번째를 선택하는 방식으로 접근했습니다. 하지만 그림의 2와 6을 보면 i와 i+1이 항상 달라야 할 필요는 없습니다.

• 조금 더 이해하기 쉽게 다음과 같은 그래프가 아닌 상황을 생각해 보겠습니다. [10,2,3,11,7]
  여기서도 하나 선택하고 하나 건너뛰는방식이 아니라 10과 11을 선택해야 합니다. 이 문제는 dp[i] = i번째 숫자까지를 고려했을 때 조건을 만족하면서 만들 수 있는 최댓값으로 정의하면 문제를 풀 수 있습니다.
  dp[1] = 10입니다.
  dp[2] = 2를 선택하거나 10을 선택할 수 있습니다. 10을 선택하는 게 더 큽니다.
  dp[3] = 3을 선택하면거나 선택하지 않을 수 있습니다.
  3을 선택하면 2를 선택할 수 없습니다. 2를 선택하지 못하면 1을 반드시 선택해야 하기 때문에 arr[3]+dp[1]이 됩니다.
  3을 선택하지 않으면 dp[2]와 동일합니다.
  ... 이런 식으로 점화식을 풀어 문제를 해결할 수 있습니다.

• 우리 문제에서는 다음과 같이 생각할 수 있습니다. dp[i]를 계산할 때 i를 선택하거나 i를 선택하지 않을 수 있습니다.
  i를 선택하지 않으면 dp[i]는 dp[i의 자식]들의 합과 동일합니다.
  i를 선택하면 dp[i]는 arr[i] + dp[i의 자식의 자식]들의 합과 동일합니다.
  이때 dp[x]는 x를 선택했다는 의미가 아닙니다. x를 선택했을수도 있고 안했을수도 있지만 어쨌든 우수 마을끼리는 인접한 상태입니다.

• 구체적인 계산은 다음과 같을 겁니다.
  dp[1] = max(dp[2], arr[1] + dp[3] + dp[6])
  dp[2] = max(dp[3]+dp[6], arr[2] + dp[4] + dp[7])
  dp[3] = max(dp[4], arr[3] + dp[5])
  dp[4] = max(dp[5], arr[4])
  dp[5] = arr5
  dp[6] = max(dp[7], arr[6])
  dp[7] = arr7

• dp[i]를 i를 선택한 게 아니라 i까지 고려했을 때의 최댓값으로 설정하는 게 가장 중요한 부분인거 같습니다.

정답

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Map<Integer,List<Integer>> graph = new HashMap<Integer,List<Integer>>();
		int[] people = new int[N+1];
		StringTokenizer st = new StringTokenizer(br.readLine());		
		for (int i = 1; i <= N; i++) {
			people[i] = Integer.parseInt(st.nextToken());
		}
		for (int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			makeGraph(graph,a,b);
			makeGraph(graph,b,a);
		}
		int[] dp = new int[N+1]; // i번째 값까지 고려했을 때 조건을 만족하는 가장 큰 값
		boolean[] v = new boolean[N+1];
		v[1] = true;
		Node root = new Node(1);
		root = makeTree(root,graph,N,v,people,dp);
		System.out.println(dp[1]);
//		System.out.println(graph.toString());
//		System.out.println(root.toString());
//		System.out.println(Arrays.toString(dp));


	}
	public static Node makeTree(Node now, Map<Integer,List<Integer>> graph, int N, boolean[] v, int[] people, int[] dp) {

	    // now를 선택한 경우
		int selectedNow = people[now.num];
        // now를 선택하지 않은 경우
		int notSelectedNow = 0; 
		if(graph.containsKey(now.num)) {
			for (int next : graph.get(now.num)) {
				if(v[next]) continue;
				v[next] = true;
				Node c = makeTree(new Node(next),graph,N,v,people,dp);
				now.child.add(c);
				// now를 선택하지 않은 경우
				notSelectedNow += dp[c.num];  
				// now를 선택한 경우
				if(!c.child.isEmpty()) {
					for (int i = 0; i < c.child.size(); i++) {
						selectedNow += dp[c.child.get(i).num];						
					}
				}
			}
		}
		dp[now.num] = Math.max(selectedNow, notSelectedNow);
		return now;
	}

	public static void makeGraph(Map<Integer,List<Integer>> graph, int from, int to) {
		if(graph.containsKey(to)) {
			graph.get(to).add(from);			
		}else {
			List<Integer> temp = new ArrayList<>();
			temp.add(from);
			graph.put(to, temp);
		}
	}
	
	public static class Node{
		int num;
		List<Node> child = new ArrayList<Node>();
		public Node(int num) {
			super();
			this.num = num;
		}
		@Override
		public String toString() {
			return "Node [num=" + num + ", child=" + child + "]";
		}
	}
}