[Algo] 백준 24230 트리 색칠하기 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/24230

메모리 : 102048KB

시간 : 1748ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static List<List<Integer>> list;
    static int N, ans;
    static int[] color;
    static boolean[] check, tmp;

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 정점의 개수
        color = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            color[i] = Integer.parseInt(st.nextToken());
        }
        list = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }
        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());
            list.get(a).add(b);
            list.get(b).add(a);
        }
        // 1번에 색칠한경우 cnt 1세고시작
        ans = color[1] == 0 ? 0 : 1;
        // 루트가 항상 1번
        check = new boolean[N + 1];
        check[1] = true;
        dfs(1);
        System.out.print(ans);
    }

    private static void dfs(int num) {
        for (int i = 0; i < list.get(num).size(); i++) {
            // 부모의 색과 자식의 색이 다르면 칠했다
            int node = list.get(num).get(i);
            if (!check[node]) {
                check[node] = true;
                if (color[num] != color[node]) {
                    ans++;
                }
                dfs(node);
            }
        }
    }
}

풀이

트리를 순회하며 부모노드와 자식노드의 색이 다른 경우 개수를 세주면 된다. 부모노드의 색을 자식노드가 따라간 경우 색칠하지 않아도 되는데, 자식노드의 색이 다르면 그 자식노드부터 색칠한 것이기 떄문이다! 맨 처음에 루트노드에 색칠한 경우까지 빠지지않고 세주면 바로 정답이다.