[백준] 9489번 사촌 (C++)

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

 

 

이 문제는 N개의 노드 수와 사촌을 구해야 하는 K노드가 주어진다.

 

이후 트리의 관계가 주어질때 특정 노드 K의 사촌의 수를 구해야 한다.

 

이 문제에서 사촌이랑 두 노드의 부모는 다르지만, 두 부모가 형제일때 두 노드를 사촌이라고 한다.

 

위 사진에서 노드 15를 기준으로 부모는 4이며

 

부모 4의 형제는 3과 5이다.즉 3의 자식들과 5의 자식들은 노드 15와 사촌의 관계가 성립되기 때문에

5가 출력되어야 한다.

 

그렇다면 8, 9, 15, 30, 31, 32의 노드들의 공통점은 무엇일까??

 

자세히 살펴보면 부모의 부모 즉 2단계의 부모는 1로 같다.

 

따라서 부모의 부모가 같으며 해당 노드의 부모가 다르면 사촌이 성립된다는 것이다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e11

struct coordinate {
    int x;
    int y;
    int r;
};

struct halloween {
    int cnt;
    int score;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, K;

void solve(int parent[], int arr[]) {
    int answer = 0;

    if(K == arr[0]) {
        answer = 0;
    }
    else {
        for(int i = 0; i < N; i++) {
            if(parent[parent[arr[i]]] == parent[parent[K]] && parent[arr[i]] != parent[K]) {
                answer++;
            }
        }
    }

    cout << answer << "\n";
}

void input() {
    while(true) {
        cin >> N >> K;

        if(N == 0 && K == 0) return;

        int parent[1000001];
        int arr[1000001];

        int Node = -1;
        int idx = -1;
        for(int i = 0; i < N; i++) {
            cin >> arr[i];

            int a = arr[i];

            if(i == 0) {
                Node = a;
                parent[a] = -1;
            }
            else {
                if(Node + 1 == a) {     // 같은 집합
                    parent[a] = arr[idx];
                    Node = a;
                }
                else {
                    Node = a;
                    idx++;
                    parent[a] = arr[idx];
                }
            }
        }

        solve(parent, arr);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}