[BOJ/Gold 5] 백준 24230 트리 색칠하기(C++)

문제 링크

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

24230번: 트리 색칠하기

 

문제

정점이 N개인 트리가 있다. 정점에는 1부터 N까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다.

하나의 정점에 색칠하면 해당 정점 아래 있는 모든 정점이 같은 색으로 칠해진다. 색은 섞이지 않고 색칠할 때마다 그 색으로 덮어진다. 단, 하얀색으로 색칠할 수는 없다.

아래 그림처럼 정점 10개로 구성된 트리가 있다고 가정을 해보자.

 

[그림 1] 하얀색으로 칠해져 있는 트리

3번 정점을 노란색으로 칠하면 그 아래 있는 정점 5, 6, 8, 9, 10 모두 노란색으로 칠해진다.

 

[그림 2] 정점 3에 노란색을 칠한 후 트리의 상태

그리고 정점 5에 파란색을 칠한다면 그 아래 있는 정점 8, 9, 10 모두 파란색으로 칠해진다.

 

[그림 3] 정점 5에 파란색을 칠한 후 트리의 상태

입력으로 트리의 정보와 정점의 색 정보가 주어진다. 색 정보는 음이 아닌 정수로 주어지며 값이 0인 경우는 항상 하얀색을 의미한다.

하얀색을 제외한 색만 사용해서 모든 정점을 주어진 색으로 칠하고 싶을 때 최소 몇 번 색을 칠해야 모든 정점을 원하는 색으로 칠할 수 있는지 구해보자.

입력

첫째 줄에 트리를 구성하는 정점의 개수 (1 ≤ N ≤ 200,000)이 주어진다.

둘째 줄에 1번 정점부터 N번 정점까지 각 색 정보 Ci (0 ≤ Ci ≤ N)가 공백으로 구분되어 주어진다.

셋째 줄부터 N - 1개의 줄에 걸쳐 연결된 두 정점 a, b(1 ≤ a, b ≤ N, a ≠ b)가 공백으로 구분되어 주어진다.  

모든 정점을 칠할 수 있는 입력만 주어진다.

출력

하얀색을 제외한 색만 사용해서 모든 정점을 원하는 색으로 칠하기 위해 최소 몇 번 칠하면 되는지 출력한다.

예제 입력 1

7
0 0 2 0 1 2 2
1 2
1 3
1 4
2 5
3 6
3 7

예제 출력 1

2

예제 입력 2

10
0 0 1 0 2 1 0 2 2 2
3 1
1 4
9 5
10 5
1 2
3 6
3 5
5 8
4 7

예제 출력 2

2

알고리즘 분류

• 그래프 탐색

풀이

노드의 색깔이 정해지면 자식 노드들 모두 같은 색으로 칠해지게 되므로 자식 노드가 하얀색인 일은 없다.

따라서 부모 노드와 자식 노드의 색깔이 다르면 새로운 색을 칠해야 한다.

그리고 1번 노드가 하얀색이 아닐 경우에도 색을 칠해야 한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 200001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, A, B;
int C[MAX];
vector<int> Edge[MAX];
int Answer;

void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> C[i];
    }
    for (int i = 0; i < (N - 1); i++) {
        cin >> A >> B;
        Edge[A].push_back(B);
        Edge[B].push_back(A);
    }
}

void DFS(int Now, int Prev) {
    for (int i = 0; i < Edge[Now].size(); i++) {
        int Next = Edge[Now][i];
        if (Next == Prev) {
            continue;
        }
        if (C[Now] != C[Next]) {
            Answer++;
        }
        DFS(Next, Now);
    }
}

void settings() {
    if (C[1] != 0) {
        Answer++;
    }
    DFS(1, 0);
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}