핵심

• 3번 조건으로 많이 헤맸다.
• 문제의 1번 조건에 의해 3번 조건은 불만족 시 모순이 된다
  • A - B - C 로 연결되어 있다고 해보자
  • A와 C가 모두 우수로 선정되지 않았을 때
  • B도 우수로 뽑히지 않은 것이 최대라고 가정해보면
  • B를 우수로 뽑았을 때 더 값이 커지므로 모순이 됨을 확인할 수 있다.
• 따라서 3번 조건을 고려할 필요가 없음.
  • 이거 생각하느라 엄청 오래 걸렸다

코드

package Baekjoon;

import java.io.*;
import java.util.*;

public class Algo1949 {

    static int N;
    static int[] population;
    static ArrayList<Integer>[] map;
    static int[][] memo;
    static int result = 0;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N = Integer.parseInt(br.readLine());
        population = new int[N+1];
        map = new ArrayList[N+1];
        memo = new int[2][N+1];
        for(int i=0; i<=N; i++) map[i] = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            population[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=1; i<=N; i++) {
            memo[1][i] = population[i];
        }

        for(int i=0; i<N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            map[v1].add(v2);
            map[v2].add(v1);
        }

        //0, 1을 써서 사용한 경우와 안한 경우를 나눈다
        //만약 이전에 1, 즉 우수마을로 지정이 되었으면 0으로 무조건 가야함
        //하지만 0이었으면, 0 1 둘다 됨
        dfs(1, 0);
        System.out.println(Math.max(memo[0][1], memo[1][1]));
    }

    private static void dfs(int current, int parent) {
        for(int next : map[current]) {
            if(next==parent) continue;
            dfs(next, current);
            memo[1][current] += memo[0][next];
            memo[0][current] += Math.max(memo[0][next], memo[1][next]);
        }
    }
}

• 추가적으로 트리 순회할 때 dfs 돌면서 parent를 통해 순회여부를 판단하는 테크닉 사용
  • visit 배열 선언할 필요가 없어서 일반적으로 공간복잡도에서 이득
    • 스택에 로컬변수들 쌓이니까 일렬로 된 트리의 경우 다를바 없음.