[BOJ/C++] 9489: 사촌

🏅 GOLD 4

✏️ 1차 솔루션

• 각 노드의 부모 배열에 저장
• 각 노드의 깊이 배열에 저장
• 부모 노드가 될 수 있는 노드는 큐로 관리

⭐️ 루트 노드 다음 노드부터 탐색 시작 - 입력 받으면서 탐색하기
⭐️ 연속적으로 증가하는 숫자들은 같은 부모를 갖게 되며 입력받은 수는 무조건 오름차순이기 때문에 앞에 입력받는 수일수록 자식이 먼저 배치될 수밖에 없기 때문에 부모가 될 수 있는 노드는 큐로 관리
⭐️ 이전 노드와 현재 노드의 부모 노드를 변수로 저장해두며 관리

1. 첫번째 탐색이거나 현재 노드가 이전 노드와 연속적인 숫자가 아니면 부모를 갱신해주기 ➡️ 큐에서 꺼내기
2. 현재 노드의 부모 & 깊이 기록
3. 현재 노드도 부모 노드가 될 수 있기 때문에 큐에 push
4. 다음 노드 탐색을 위해 현재 노드를 이전 노드 변수에 저장
5. 모든 노드에 대해 k 와 같은 깊이면서 부모가 다르면 사촌으로 count

🚨 1차 trouble

테케는 맞는데 틀렸다고 뜸..

✏️ 최종 솔루션

깊이로 사촌을 따지는 것이 아니라 삼촌들의 자식들을 사촌으로 따져야하기 때문에 각 노드의 자식과 부모를 기록해두는 것이 관건이었음
깊이 기록이 아니라 자식 기록으로 방법을 대체

📌 self feedback

❗️ 최대 개수가 1,000,000 으로 인접리스트로 구현하면 너무 크기 때문에 int 형을 key 로 하고 vector 을 value 로 하는 map 에 자식을 관리하는 것이 포인트였음 ➡️ 자꾸 out of index 오류남;;
큐로 예비 부모 노드를 기록해두는 것은 좋은 시도였음

✏️ 최종 code

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n,k;
    while(1) {
        int parents[1000001];   // 각 노드의 부모 저장
        map<int,vector<int>> child; // 각 노드의 자식 저장
        int root;

        queue<int> q;

        memset(parents, 0, sizeof(parents));
        child.clear();

        cin >> n >> k;

        if(n==0 && k==0) break;

        cin >> root;

        if(k==root) {
            cout << 0 << endl;  // k가 루트노드이면 사촌이 없음
            continue;
        }

        q.push(root);

        int pre=0;  // 이전 노드 저장
        int par=root;   // 현재 노드의 부모 노드 저장

        for(int i=1;i<n;i++) {
            int cur;
            cin >> cur;

            // 첫 탐색이거나 현재 노드가 이전 노드와 같은 집합에 속하지 않는 노드이면 현재 노드의 부모 갱신
            if(pre==0 || pre+1!=cur) {
                par=q.front();
                q.pop();
            }

            parents[cur]=par;    // 현재 노드의 부모 저장

            // 부모의 자식에 현재 노드 저장
            vector<int> v;

            if(child.count(par)>0) v=child[par];
            v.push_back(cur);
            child[par]=v;

            q.push(cur);
            pre=cur;
        }

        int ans=0;
        par=parents[k];
        int grand=parents[par];
        vector<int> v;
        v=child[grand]; // 삼촌 vector
        for(int i=0;i<v.size();i++) {
            int c=v[i];  // 삼촌 노드

            if(c==par) continue;

            ans+=child[c].size();
        }

        cout << ans << endl;
    }

}