(C++) 백준 1068.트리

백준 1068번 트리 (C++)

---

문제 설명

• 문제에서는 각각 노드의 부모노드를 알려주는 방식으로 트리를 제공한다. 해당 트리에서 특정 번호의 노드를 제거 했을때 하위의 자식 노드들은 사라지게 되고 이때 leaf node의 개수를 출력해야한다.

---

문제 풀이

• 입력 방식:

  • 편의상 각각의 노드 번호에 +1을 하여 1번~N번 노드로 정하고 풀이했다.
  • 루트 노드부터 방문해서 내려가기 위해서 루트 노드의 번호는 따로 vector에 저장했다.
  • 부모 노드부터 자식 노드까지 탐색하기 위해서 vector 배열을 이용해서 배열 인덱스에는 부모노드 해당 배열의 벡터 인덱스에는 자식 노드를 표시하였다.

• 알고리즘 선택:

  • 더 이상 내려갈 수 없는 경우에 리프 노드의 개수를 +1 해주면 되기에 bfs를 사용했다. 루트 노드를 기준으로 dfs 혹은 bfs를 사용하든 방문 처리만 해준다면 큰 상관이 없지만 bfs를 연습하기 위해서 bfs를 사용했다.

• 노드 제거:

  • 제거하는 노드를 입력 받은 후에는 방문하지 않아야 하기에 방문 처리를 미리 해주는 방법을 택했다. 제거할 노드의 자식 노드가 저장되어 있는 벡터는 굳이 clear 하지 않아도 되지만, 지우는 것이 메모리 절약 방안이라 생각하여 지웠다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define FOR(i,N) for(int i=1; i<=N; i++)
int N, removeNode;
vector<int> tree[51];
int vis[51];
vector<int> rootNodes;
int bfs(int start) {
    int childNodeCount = 0;
    queue<int> q;
    q.push(start);
    vis[start] = 1;
    while(!q.empty()) {
        int n = q.front();
        q.pop();
        bool isLeaf = true;
        for(int i=0; i<tree[n].size(); i++) {
            if(vis[tree[n][i]]==0) {
                q.push(tree[n][i]);
                vis[tree[n][i]] = 1;
                isLeaf = false;
            }
        }
        if(isLeaf) {
            childNodeCount++;
        }
    }
    return childNodeCount;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    FOR(i,N) {
        int parent; cin >> parent;
        if(parent!=-1) {
            tree[parent+1].push_back(i);
        }
        else rootNodes.push_back(i);
    }
    cin >> removeNode;
    tree[removeNode+1].clear();
    vis[removeNode+1] = 1;
    int ans = 0;
    for(auto&i:rootNodes) {
        if(vis[i]==0) ans+=bfs(i);
    }
    cout << ans;
    return 0;
}