[BOJ 1068] 트리

1068번: 트리

 

1. 문제

 

각 예제별 트리의 모습을 입력 오른쪽에 그림으로 표현하였다.

 

2. 구현 아이디어 1 - 틀렸습니다

그래프를 표현하는 방법에는 인접 행렬과 인접 리스트가 있는데, 인접 리스트 방식을 사용하였다.

map 자료구조를 사용하여 key는 부모 노드, value는 자식 노드의 배열로 하였다.

 

재귀(DFS)를 사용하여 자식 노드가 없을 때를 종료 조건으로 하고 종료 조건일 때마다 리프 노드의 개수를 +1하도록 재귀 함수를 구현하였다.

 

만약 제거할 노드가 루트 노드와 같다면 재귀를 돌 필요 없이 리프 노드가 0개가 되므로 0을 출력하고 바로 return하도록 하였다.

 

재귀 코드

void go(int k) {
    // 자식 노드가 없으면 ret을 1 더한다
    if (mp[k].empty()) {
        ret++;
        return;
    }

    // 자식 노드들에 대해 재귀를 진행한다
    for (auto elem : mp[k]) {
        if (elem == target) continue;
        go(elem);
    }
}

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int n; // 노드의 개수
int target;

map<int, vector<int>> mp; // 인접 리스트
int ret; // 리프 노드의 개수
int root; // 루트 노드

void go(int k) {
    // 자식 노드가 없으면 ret을 1 더한다
    if (mp[k].empty()) {
        ret++;
        return;
    }

    // 자식 노드들에 대해 재귀를 진행한다
    for (auto elem : mp[k]) {
        if (elem == target) continue;
        go(elem);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for (int i = 0; i < n; ++i) {
        int temp;
        cin >> temp;

        // 입력이 -1일 때 root 변수에 루트 노드를 저장
        if (temp == -1) {
            root = i;
            continue;
        }
        mp[temp].push_back(i);
    }

    cin >> target;

    // 제거할 노드가 루트 노드와 같다면 리프 노드는 0개
    if (target == root) {
        cout << 0 << "\n";
        return 0;
    }

    // 제거할 노드의 자식 노드 배열을 비운다
    mp[target].clear();

    go(root);

    cout << ret << "\n";

    return 0;
}

 

 

3. 구현 아이디어 2 - 맞았습니다 !!

 

수많은 반례를 거쳐 ... 문제를 풀었다.

아래는 내가 문제를 해결하기 위해 찾은 반례 모음이다

 

반례 모음

💡 Tip: 99%쯤 가서 틀릴 경우, 극단적인 case일 때 통과하지 못하는 것이다

// 노드를 제거한 후 루트 노드만 남았을 때
Input:
2
-1 0
1

Ans:
1

// 트리가 한 줄로 이어졌을 경우
Input:
4
-1 0 1 2
1

Ans:
1

Input:
9
-1 0 0 5 2 4 4 6 6
4

Ans:
2

 

수정 코드

재귀의 종료 조건으로 자식 노드가 있지만, 제거된 노드 하나만 있을 때를 추가하여 target 노드가 제거되어 target 노드의 부모가 리프 노드가 될 때 ret을 1 더해주도록 구현하였다.

#include <bits/stdc++.h>

using namespace std;

int n; // 노드의 개수
int target;

map<int, vector<int>> mp;
int ret;
int root;

void go(int k) {
    if (mp[k].empty() || (mp[k].size() == 1 && mp[k][0] == target)) {
        ret++;
        return;
    }

    for (auto elem : mp[k]) {
        if (elem == target) continue;
        go(elem);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for (int i = 0; i < n; ++i) {
        int temp;
        cin >> temp;

        if (temp == -1) {
            root = i;
            continue;
        }
        mp[temp].push_back(i);
    }

    cin >> target;
    if (target == root) {
        cout << 0 << "\n";
        return 0;
    }

    mp[target].clear();

    go(root);

    cout << ret << "\n";

    return 0;
}