[BOJ 1949] 우수마을 (Java, DP)

 

 

---

문제 링크 

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

1949번: 우수 마을

---

문제 풀이 

- 인접 리스트 사용하여 시간 복잡도 O(V + E) = O(10,000 + 9,999)

- 트리이기 때문에 간선의 수 = 노드의 수 - 1 

- DFS 방식으로 리프 노드 구하는 문제에서 응용하는 문제로 2차원 배열로 방문 여부에 따라 조건 처리를 하게 된다

- 시작 노드는 1로 해서 최종적으로 DP[1][0], DP[1][1] 중 최대값이 최대 인구에 해당한다

 

DP[i][0] = i번째 마을이 우수 마을이 아닌 경우, 자식 노드가 우수 마을인 경우와 아닌 경우 중 최대 인구수를 합함
DP[i][1] = i번째 마을이 우수 마을로 지정할 경우, 자식 노드가 우수 마을이 아닌 경우와 i번째 마을 인구수를 합함 

 

5,7번이 각각 리프노드

 

	1	2	3	4	5	6	7
DP[i][0]					0		0
DP[i][1]					2,000		7,000

 

	1	2	3	4	5	6	7
DP[i][0]				2,000	0	7,000	0
DP[i][1]				1,000	2,000	2,000	7,000

 

	1	2	3	4	5	6	7
DP[i][0]			2,000	2,000	0	7,000	0
DP[i][1]			6,000	1,000	2,000	2,000	7,000

 

	1	2	3	4	5	6	7
DP[i][0]		13,000	2,000	2,000	0	7,000	0
DP[i][1]		12,000	6,000	1,000	2,000	2,000	7,000

 

	1	2	3	4	5	6	7
DP[i][0]	13,000	13,000	2,000	2,000	0	7,000	0
DP[i][1]	14,000	12,000	6,000	1,000	2,000	2,000	7,000

 

결국 1 , 3 , 5 , 7 노드가 선택되면 최대 노드가 된다

 

 

추가.

i을 루트로 하는 서브 트리에서 i을 선택하지 않는 경우가 3가지 나오는데, 아래 기술 블로그 참고함

https://lotuslee.tistory.com/96

[백준 1949번] 우수 마을 (java)

---

제출 코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();
    
    static int ROOT = 1;
    static int N;
    static List<Integer>[] ADJ;
    static int[] CITIZEN;
    static int[][] DP;

    public static void main(String[] args) throws IOException {
        input();

        pro();

        output();
    }

    private static void input() {
        N = inputProcessor.nextInt();

        CITIZEN = new int[N + 1]; // 주민 수
        for(int i = 1; i <= N; i++) {
            CITIZEN[i] = inputProcessor.nextInt();
        }

        ADJ = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++) {
            ADJ[i] = new ArrayList<>();
        }

        for(int i = 1; i <= N - 1; i++) {
            int a = inputProcessor.nextInt();
            int b = inputProcessor.nextInt();

            ADJ[a].add(b);
            ADJ[b].add(a);
        }
    }

    private static void pro() {
        DP = new int[N + 1][2];
        
        dfs(ROOT, - 1);

        sb.append(Math.max(DP[ROOT][0], DP[ROOT][1]));
    }

    private static void dfs(int node, int prev) {
        DP[node][1] = CITIZEN[node];

        for(int child : ADJ[node]) {
            if(child == prev) continue;

            dfs(child, node);

            DP[node][0] += Math.max(DP[child][0], DP[child][1]);
            DP[node][1] += DP[child][0];
        }
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}