[백준 1068 C++][G5] 트리

⭐️난이도

골드 5

---

 

⭐️문제

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

트리의 노드의 개수와 각 노드의 부모가 주어진다. 입력으로 "지울 노드의 번호"가 주어진다.

입력으로 주어진 노드를 지우고 난 후, 트리에 남은 노드들 중 리프 노드(자식이 없는 노드)의 개수를 출력하면 되는 문제이다.

1068번: 트리

---

⭐️ 내 풀이 &  Code

분류가 트리로 되어 있어 처음엔 이진 트리라고 생각했고, 이진 트리를 이용하여 문제를 풀 생각이었다. 하지만 잘 읽어보니 해당 트리가 이진 트리라는 보장이 없었다.

 

그래서 생각한 방법은 vector 컨테이너를 사용하는 것이었다. DFS와 BFS에서도 vector를 이용해서 인접 리스트를 구현했는데, 트리도 결국은 그래프의 일종이므로 비슷하게 사용할 수 있다고 생각했다.

 

📌필요한 기능

    ① 각 노드마다 자식을 몇 개 갖고 있는가?

        → vector안에 넣어 놓는다면 .size()를 통해 자식의 갯수를 알 수 있다.

        vector<int> childInfo[MAX]를 통해 자식 정보 저장

    ② 해당 노드를 삭제 할 때에 노드 밑에 딸려 있는 서브 트리들까지 모두 연결을 끊어야 한다.

        → 이 부분에서 재귀적 방법(DFS)를 사용해야 한다고 생각했다.

 

#include <iostream>
#include <vector>

#define MAX 50 + 1
#define INF 100000000
using namespace std;

int n, root, deleteNode; // 노드의 갯수, 루트노드의 번호
int result = 0;
int parentInfo[MAX]; // i번째 노드의 부모노드 번호
bool isVisited[MAX];
vector<int> childInfo[MAX]; // i번째 노드의 자식노드 번호들을 저장


void input(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        int tmp;
        scanf("%d", &tmp); // i번째 노드의 부모 노드 번호를 입력 받는다.
        parentInfo[i] = tmp; // i번째 노드의 부모 노드 정보 저장
        if(tmp == -1){
            root = i;
        }
        else{
            childInfo[tmp].push_back(i);
        }
    }
    scanf("%d", &deleteNode); // 지우고자하는 노드의 번호 입력
}

void DFS(int idx){
    // DFS를 통해 제일 깊이가 깊은 노드까지 먼저 간 후, 해당 노드부터 자식 노드와의 연결을 끊어준다.
    isVisited[idx] = true;

    for(int i = 0; i < childInfo[idx].size(); i++){
        int next = childInfo[idx][i]; // 연결되어 있는 자식 노드
        if(!isVisited[next]){ // 아직 방문하지 않은 노드라면
            DFS(next); // 자식 노드를 방문한다
            childInfo[next].clear(); // 연결을 끊어준다.
        }
    }
    childInfo[idx].clear();
}

int main(void) {

    int parent;

    input();
    if(deleteNode == root){ // 지우고자 하는 노드가 루트 노드인 경우
        result = 0; // 트리 전체가 지워지므로 리프 노드는 없다
    }
    else{
        DFS(deleteNode); // DFS를 통해서 노드를 삭제한다.
        parent = parentInfo[deleteNode]; // 지우고자하는 노드의 부모 노드 번호
        for(int i = 0; i < childInfo[parent].size(); i++){
            if(childInfo[parent][i] == deleteNode){ // 부모노드의 자식 정보 중에서 지우고자 하는 노드를 제거한다
                childInfo[parent].erase(childInfo[parent].begin() + i);
                break;
            }
        }
        // 방문하지 않은 노드(DFS를 거치지 않은 노드)임과 동시에 자식의 갯수가 0이라면 리프 노드
        for(int i = 0; i < n; i++){
            if(!isVisited[i] && childInfo[i].size() == 0){
                result++;
            }
        }
    }

    printf("%d", result);

    return 0;
}

1068.jpg

1.05MB