G24230. 트리 색칠하기

문제

제출 코드

• 사용 알고리즘 : 트리, DFS

상위 노드를 색칠하면 하위노드들까지 모두 색칠되므로, 상위 색과 다른 색인 하위 노드들에 대해서만 색을 다시 칠해주면 되기에 dfs로 탐색하며 그 횟수를 세어 주었다.

상위노드의 색과, 정답지 색 정보만 알면 색을 칠하는 횟수를 구할수 있기에, 현재 노드들의 색 상태는 따로 저장할 필요가 없었다.

package gold;

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 G24230_paintingTree {
	static int N, cnt=0;
	static int[] answer;
	static List<Integer>[] nodes;
	static boolean[] visit;

	static void dfs(int node, int color) {
		visit[node] = true;
		int paint = color;
		if(answer[node] != color) {
			paint = answer[node];
			cnt++;
		}
		for(int n : nodes[node]) {
			if(!visit[n]) dfs(n, paint);
		}
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		answer = new int[N+1];
		nodes = new List[N+1];
		visit = new boolean[N+1];

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

		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());
			nodes[a].add(b);
			nodes[b].add(a);
		}

		dfs(1, 0);

		System.out.println(cnt);

	}

}