[백준 9489] - 사촌(C++)[골드4]

문제

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

9489번: 사촌

---

🔎문제 설명

K의 사촌을 구하는 문제입니다.

사촌의 정의는 이제 부모가 다르지만, 할아버지, 할머니가 같은 사람들입니다.

 

부모를 저장하기 위해서 parent 배열을 사용했습니다.

parent [idx]는 idx의 부모의 숫자가 저장되어 있습니다.

 

같은 부모인지 아닌지를 판단하기 위해서는 숫자의 차이를 비교하면 알 수 있습니다.

연속된 입력이 아니라면 다른 부모라는 뜻입니다.

1, 3,4,5가 입력이라면 1 / (3,4,5)가 되고, 즉 3,4,5의 부모는 1이 되는 걸 알 수 있습니다.

1. 첫 번째 입력이라면, 그 숫자를 루트 노드로 지정해 줍니다.
2. 그리고 이전 입력값과 현재 입력값 비교
   1. 차이가 1이라면, 같은 부모를 가지고 있다는 뜻이기에, parent [idx] = parent_idx로 지정해 줍니다.
   2. 차이가 1이 아니라면, 다른 부모를 가지고 있다는 뜻입니다.
      1. 그렇다면 parent_idx(부모 번호)를 증가시켜 주고, parent [idx]= node [parent_idx]가 됩니다. 

위의 작업을 n번한 뒤, 우리는 k의 사촌을 찾아야 합니다.

k의 사촌은 부모가 다르고, 할아버지가 같아야 하기에, 다음과 같은 식이 도출됩니다.

parent [parent [node [i]]]==parent [parent [k]] //할아버지, 할머니
parent [node [i]]!= parent [k] //부모님
위 2가지 조건을 만족하면 node [i]는 사촌입니다!

---

💻전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
int main()
{
    while (1)
    {
        cin >> n >> k;
        if (n == 0 && k == 0) // 종료해야함.
            break;
        int parent_idx = -1, before = 0, ans = 0, data;
        int parent[1000001];
        vector<int> node;
        for (int i = 0; i < n; i++){
            cin >> data;
            node.push_back(data);
            if (i == 0){ // 첫입력이면 루트노드임.
                before = data;
                parent[data] = -1; // 자기가 자신의 부모임.
            }
            else{
                if (before + 1 == data){ // 같은집합.
                    parent[data] = node[parent_idx];
                    before = data;
                }
                else{
                    before = data;
                    parent_idx++;
                    parent[data] = node[parent_idx]; // data의 부모를 넣어줌.
                }
            }
        }
        // parent[data]에는 data의 부모가 있습니다.우리는 k의 사촌 수를 찾아야 합니다.
        if (k == node[0]){
            ans = 0;
        }
        else{
            for (int i = 0; i < node.size(); i++){
                //  k와 부모가 다르고, k의 부모들과 부모가 같아야합니다.
                if (parent[parent[node[i]]] == parent[parent[k]] && parent[node[i]] != parent[k]){
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }
}

 

😀느낀 점

• 구조체로 트리를 선언해서 풀고 싶었지만, 잘 기억이 안 나서 익숙한 배열로 풀었다.
• 하지만 굳이 트리 형태로 만들어서 풀 필요까지는 없는 것 같다.