[백준 / Java] 24230번: 트리 색칠하기 (골드5)

문제 풀이 날짜: 2023.10.13
포스트 작성일: 2023.10.16

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 24230번: 트리 색칠하기 (골드5)

 

키워드

트리의 특징, BFS

 

풀이 접근법

• 단순 DFS로 탐색하면 시간 초과가 난다. 또, 트리를 양방향 그래프로 생성하지 않으면 반례가 생기므로 주의한다.
• 그래프로 구현한 트리를 루트부터 탐색하면서, 답안으로 주어진 색과 동일하다면 넘어가고, 동일하지 않다면 부모노드의 색깔로 색칠하며 리프 노드까지 탐색한다.
  • 자식 노드를 칠할 때는, 부모 노드의 색깔을 가져다가 쓴다.(colors[child] = prevColors[parent])
  • 이때, 각 노드마다 부모노드의 색을 기억해야 하므로 별도의 배열을 선언해준다.
• 부모노드를 다시 칠하면 별도로 기억해두었던 부모노드의 색깔(prevColors)도 변경되므로 이를 갱신해주어야 한다. 
  • prevColors[자기자신]를 갱신시키지 않아 0으로 남아있을 경우 불필요한 도색이 또 필요하게 된다. 
  • 그러므로 부모 노드의 색을 저장하는 prevColors[자기자신] 값은 항상 color[자기자신]로 갱신되어야 한다. 그렇지 않으면 모든 자식노드들에게 연쇄적으로 색이 칠해지지 않으니 주의한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static int N;
	
	private static int[] colors;
	private static int[] prevColors;
	private static int[] targets;
	
	private static boolean[] visited;
	private static List<Integer>[] tree;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		
		colors = new int[N + 1];
		prevColors = new int[N + 1];
		targets = new int[N + 1];
		
		visited = new boolean[N + 1];
		
		tree = new LinkedList[N + 1];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 1; i <= N; i++) {
			targets[i] = Integer.parseInt(st.nextToken());
			tree[i] = new LinkedList<>();
		}

		for(int i = 0; i < N - 1; i++) {
			String[] temp = br.readLine().split(" ");

			int u = Integer.parseInt(temp[0]);
			int v = Integer.parseInt(temp[1]);
			
			tree[u].add(v);
			tree[v].add(u);
		}
		
		int count = BFS(1);
		
		System.out.print(count);
	}
	
	private static int BFS(int start) {
		Queue<Integer> queue = new ArrayDeque<>();
		int count = 0;
		
		queue.add(start);
		visited[start] = true;

		while(!queue.isEmpty()) {
			int parent = queue.poll();
			
			if(colors[parent] != targets[parent]) {
				colors[parent] = targets[parent]; //원하는 색을 칠한다.
				prevColors[parent] = colors[parent]; //부모 노드의 색을 저장한다. => 자식 노드에도 색칠
				count++;
			}
			
			for(int child : tree[parent]) {
                if(visited[child]) { continue; }
				visited[child] = true;
                
				colors[child] = prevColors[parent]; //부모 노드의 색과 같은 것으로 칠한다.
                prevColors[child] = colors[child];
				queue.add(child);
			}
		}
		
		return count;
	}
}

---

 

참고한 링크

https://amor-fati.tistory.com/235