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

in Algorithm on 그래프 이론

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

풀이

트리가 주어지고 트리를 주어진 색으로 칠해야 한다.

한 정점에 색을 칠하면 그 정점의 하위 정점들 모두에게 같은 색을 칠한다.

따라서 루트인 1번 정점부터 시작하여 아래로 내려가면서 색이 다르면 색을 칠해줬다.

dfs탐색을 통해 먼저 자식의 부모의 색을 따라서 칠하고

원하는 색과 비교하여 색을 다시 칠했다.

메모리: 111952KB

시간: 1684ms

언어: Java 11

코드

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

public class Main {
    static int N, ans;
    static int[] arr, color;
    static ArrayList<ArrayList<Integer>> list;
    static boolean[] visit, isColored;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];
        color = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            color[i] = Integer.parseInt(st.nextToken());
        }

        list = new ArrayList<>();
        for (int i = 1; i <= N + 1; 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);
        }

        ans = 0;
        visit = new boolean[N + 1];
        dfs(1, 0);

        System.out.println(ans);
    }

    private static void dfs(int node, int prev) {
        visit[node] = true;
        arr[node] = arr[prev];

        if (arr[node] != color[node]) {
            arr[node] = color[node];
            ans++;
        }

        for (int next : list.get(node)) {
            if (!visit[next]) {
                dfs(next, node);
            }
        }
    }

}