백준 24230 c++

타이머

 

확인

문제

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

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

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

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

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

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

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

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

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

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

입력

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

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

셋째 줄부터 N−1$N - 1$개의 줄에 걸쳐 연결된 두 정점 a,b(1≤a,b≤N$a, b(1 ≤ a, b ≤ N$, a≠b)$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

 

 

점점 풀리기시작한다 ..!!!

 

#include <bits/stdc++.h>

using namespace std;

int N;

vector<pair<int,int>>color;
int visited[200001];
vector<int>graph[200001];
int ans =0 ;
int cc=0;


void dfs(int start ){


    visited[start] = 1;

    for (int i = 0; i <graph[start].size() ; ++i) {

        int next = graph[start][i];

        if(visited[next]==0 && color[start].second == color[next].second && color[next].second!=0){
            dfs(next);
        }

    }


}


int main(){
    cin >> N;

    color.push_back({0,0});

    for (int i = 1; i <=N ; ++i) {
        int a ;
        cin >> a;

        if(a>0){
            cc++;
        }

        color.push_back({i,a});

    }

    for (int i = 0; i < N-1; ++i) {
        int x, y ;

        cin >> x >> y ;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }


    for (int i = 1; i <= N; ++i) {
        if(color[i].second>0 && visited[color[i].first] ==0){
            dfs(color[i].first);
            ans++;
        }
    }

    cout << ans <<"\n";



}

 

 

문제만 봤을때는 이걸 어떻게 풀어? 라고 생각했는데

막상 천천히 그리고 따라가보면 쉬운 문제가 많은듯 하다 이 문제도 역시 그런 유형의 문제

 

이 문제에선 색깔의 갯수가 정해지지 않음 -> 하지만 어떤 노드의 밑에 있는 색깔들이 모두 바뀌어야 한다면 ? 

-> 색깔의 갯수가 정해지지 않아도 결국엔 밑에 있는 색깔들은 다 달라져야 하는거기 때문에 색깔의 갯수는 의미가 없음 

 

1. 색깔이 0이 아닌 곳의 위치와 색깔을 저장함

2. 0이 아닌곳을 찾아서 dfs를 돌림

3. 방문 안했고 다음 방문 노드 색깔이 현재 색깔과 같을 때만 앞으로감

4. 만약에 dfs가 한번 끝나면 ans ++를 통해서 답을 하나 올려줌 / 붙어있는 노드중 색깔이 같은것들의 갯수만 세면 되기 때문

5. 다음 0이 아닌 색깔을 찾아서 dfs를 돌림 만약에 방문안했으면 dfs를 돌려줌

6. 반복

7. 끝까지 돌려주고 ans 출력