[코드트리] 트리 사촌 C++

문제

https://www.codetree.ai/missions/9/problems/beard-tree?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 쪼개기

주어지는 것

n: 노드의 수, k: 사촌을 구해야 하는 노드의 번호

n개의 증가하는 수열

 

목표

특정한 노드 번호가 주어졌을 때, 그 노드의 사촌의 수를 구하는 프로그램

 

조건

증가 수열을 이용하여 트리를 만드는 방법

1. 첫 번째 정수는 트리의 루트 노드입니다.
2. 다음에 등장하는 연속된 수의 집합은 루트의 자식을 나타냅니다. 이 집합에 포함되는 수의 첫 번째 수는 항상 루트 노드+1보다 큽니다.
3. 그다음부터는 모든 연속된 수의 집합은 아직 자식이 없는 노드의 자식이 됩니다. 그러한 노드가 여러 가지인 경우에는 가장 작은 수를 가지는 노드의 자식이 됩니다.
4. 집합은 수가 연속하지 않는 곳에서 구분됩니다.

예를 들어서, 1 3 4 5 8 9 11 이라는 증가 수열이 주어지면, 집합은 1 | 3 4 5 | 8 9 | 11 같은 식으로 구분되고, 루트는 1이 되며, 자식은 3 4 5가 됩니다. 그리고 8 9는 3의 자식이, 11은 4의 자식이 됩니다.

 

두 노드의 부모가 다르지만, 두 부모가 형제일 때, 두 노드를 사촌이라고 합니다.

 

 

문제를 이해하기 위해 몇 번 읽어보았다. 이 문제에서 첫 번째로 마주하게 되는 것이 "증가하는 수열로 트리 만들기" 이다.

조건 중 1번과 4번이 중요하다고 생각되었다.

 

문제에 주어진 예시 "1 3 4 5 8 9 11"과 위의 조건으로 어떻게 트리를 만드는지 보자!

 

<트리 만들기>

1. 첫 번째 노드를 루트로 설정

2. 두 번째 노드부터 연속하지 않을 때까지 저장 + 루트노드와 연결

3. 리프노드를 오름차순으로 관리

4. 가장 앞에 있는 노드와 연속하는 구간들을 저장+연결 반복

 

<K의 사촌 노드의 수 구하기>

두 노드의 부모가 다르지만, 두 부모가 형제일 때, 두 노드를 사촌이라고 함

두 부모가 형제이기 위해서는 부모의 부모가 같아야 한다.

부모가 다르면서, 부모의 부모가 같은 노드 중 깊이가 동일한 노드들이 사촌 노드가 될 것 같다.

 

 

근데 가만히 생각해보니

 1 | 3 4 5 | 8 9 | 11라면 345는 1의 자식이고, 89는 3의 자식이고 11은 4의 자식이 된다.

항상 오름차순으로 수열이 주어지기 때문에 트리를 그렇게 복잡하게 안 만들어도 될 것 같다는 생각이 들었다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N= 1001;
const int MAX_NODE= 1000001;

int n, k, p;
int sequences[MAX_N]; // input으로 주어지는 증가하는 수열
int numOfChild[MAX_NODE]; // i번 노드의 자식의 개수
int parent[MAX_NODE]; // parent[i]: i번 노드의 부모 번호

void MakeTree(){
    p=0;
    for(int i=1; i<n; ++i){
        // 연속하는 경우
        if(i+1<n && sequences[i]+1==sequences[i+1]){
            parent[sequences[i]]=sequences[p];
            numOfChild[sequences[p]]++;
        }
        else{
            parent[sequences[i]]=sequences[p];
            numOfChild[sequences[p]]++;
            p++;
        }
    }
}

// return num of cousin node
int GetCousinNode(){
    int cnt=0;
    bool visited[MAX_NODE]={false, };
    for(int i=0; i<MAX_NODE; ++i){
        // 부모가 다르지만 두 부모가 형제인 경우(=부모의 부모가 같은 경우)
        if(parent[i]!=parent[k] && parent[parent[k]]==parent[parent[i]]){
            //cnt++;
            // 8, 9의 부모는 둘 다 3
            // 3의 자식 수를 8에서 더하고, 9에서 또 더하면 안 된다.
            if(!visited[parent[i]]){
                cnt+=numOfChild[parent[i]];
                visited[parent[i]]=true;
            }
        }
    }
    return cnt;
}

int main() {
    // input
    cin >> n >> k;
    for(int i=0; i<n; ++i){
        cin >> sequences[i];
    }

    MakeTree();

    cout << GetCousinNode() << '\n';
    return 0;
}

 

 

(+) 더 나은 풀이

그냥 부모가 다른데, 부모의 부모가 같은 경우 cnt++만 해줘도 될 것 같다는 생각이 들었다.

그런데 일부 테스트 케이스를 통과하지 못해서 위와 같이 코드를 제출했다.

제출 한 후 해설을 확인해보니, 원래 생각(cnt++만 해도 될 것 같다는 생각)과 비슷하게 풀이가 나와있었다.

해설에는 부모의 부모가 없는 경우를 처리해주는 코드가 들어가 있었다는 점이 달랐다.

해당 부분을 처리해주니 numOfChild 와 visited 배열 없이 정답이 되었다.

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N= 1001;
const int MAX_NODE= 1000001;

int n, k, p;
int sequences[MAX_N]; // input으로 주어지는 증가하는 수열
int parent[MAX_NODE]; // parent[i]: i번 노드의 부모 번호

void MakeTree(){
    p=0;
    for(int i=1; i<n; ++i){
        // 연속하는 경우
        if(i+1<n && sequences[i]+1==sequences[i+1]){
            parent[sequences[i]]=sequences[p];
        }
        else{
            parent[sequences[i]]=sequences[p];
            p++;
        }
    }
}

// return num of cousin node
int GetCousinNode(){
    int cnt=0;

    for(int i=0; i<MAX_NODE; ++i){
        if(parent[parent[k]]==0 || parent[parent[i]]==0) continue;

        // 부모가 다르지만 두 부모가 형제인 경우(=부모의 부모가 같은 경우)
        if(parent[i]!=parent[k] && parent[parent[k]]==parent[parent[i]]){
            cnt++;
        }
    }
    return cnt;
}

int main() {
    // input
    cin >> n >> k;
    for(int i=0; i<n; ++i){
        cin >> sequences[i];
    }

    MakeTree();

    cout << GetCousinNode() << '\n';
    return 0;
}