[C++] 백준 1068: 트리

문제 이해

- 리프 노드: 자식의 개수가 0인 노드

- 트리가 주어졌을 때, 노드 1개를 지울 것이다.

- 남은 트리에서 리프 노드의 개수를 구하라.

※ 단, 노드를 지울경우 그 노드와 노드의 모든 자손이 트리에서 제거된다.

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 128MB

 

<입력>

- N: 트리의 노드의 개수 (1 ~ 50)

- 각 노드의 부모

※ 부모가 없을경우, -1이 주어진다.

- 지울 노드의 번호

 

<출력>

- 노드를 지운 후 리프 노드의 개수

 

 

---

문제 풀이

이 문제의 핵심은 그래프의 방향성에 있다고 생각한다.

 

 

보통의 트리 문제는

트리도 결국 그래프의 일종이니만큼 정점을 인접 그래프로 표현할 때,

양방향으로 집어넣는다.

 

 

하지만, 이 문제의 경우 리프 노드, 즉 제일 아래의 노드가 우리의 관심사이고

위로 올라갈 필요는 전혀 없다.

아니, 오히려 방해가 된다.

 

 

그렇기에 부모에서 자식으로 가는 방향의 간선만 인접 그래프에 넣어주는 것이다.

v[parent].push_back(i);

 

 

그 후,

루트 노드부터 DFS를 진행해서 리프 노드의 개수를 찾는다.

이때, 지울 노드의 경우 미리 방문 처리를 해서 DFS 과정 중에 방문하지 않도록 한다.

 

 

dfs를 진행하며 재귀 호출을 발생시킬경우 자식이 있는 노드이므로 리프 노드가 아닐 것이고,

재귀 호출을 발생시키지 않는다면 리프 노드이다.

개수를 카운트해서 출력하도록 하자.

 

 

---

주의할 점

1. 반드시 0이 루프 노드인 것은 아니다.

예제때문에 착각할 수 있는데, 부모가 -1로 주어지는 부모가 없는 리프를 루프 노드로 설정해줘야 한다.

 

2. 만약 루프 노드를 지울경우 dfs가 작동하지 않도록 조치를 해야 한다.

 

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
#define INF 987654321

vector <int> v[55];
bool visited[55];
int cnt;

void dfs(int now){
    visited[now] = true;
    bool isLeaf = true;

    for(auto i: v[now]){
        int next = i;
        if(visited[next] == false){
            dfs(next);
            isLeaf = false;
        }
    }

    if(isLeaf) cnt++;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, roof, erased;
    cin>>n;
    for(int i = 0; i < n; i++){
        int parent;
        cin>>parent;
        if(parent != -1){
            v[parent].push_back(i);
        }else{
            roof = i;
        }
    }
    cin>>erased;
    visited[erased] = true;

    if(!visited[roof]) dfs(roof);

    cout<<cnt;
    return 0;
}

 

 

---

배운 점

트리의 그래프 탐색 문제에서 꼭 양방향으로 생각할 필요는 없다는 걸 배울 수 있었다!