[BOJ/DFS] BOJ 1068 트리 C++

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

1068번: 트리

 

문제풀이

트리에서 특정 노드를 제거했을떄 남은 리프노드의 개수를 구하는 문제이다 트리의 개수를 구하는 방법은 인접리스트를 이용하여 트리를 탐색해주면 리프노드의 개수를 구할 수 있다.

 

입력으로 인접리스트에 노드의 인덱스를 넣어준다 배열과 vector를 이용하면 인접리스트를 쉽게 구현할 수 있다.

adj[0] = {1, 2} adj[1] = {3, 4} 이렇게 부모노드와 자식노드의 리스트를 만들어준뒤 dfs 함수로 인접한 리스트를 방문해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
int n, _index, root, _remove;
vector<int> adj[51];

int dfs(vector<int> here){
    if(!here.size()) return 1;
    int ret = 0;
    for(int there: here){
        if(there == _remove) continue;
        ret += dfs(adj[there]);
    }
    return ret;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> _index;
        if(_index == -1) {
            root = i; 
            continue;
            }
        adj[_index].push_back(i);
    }
    cin >> _remove;
    if(_remove == root) cout << 0 << '\n';
    else cout << dfs(adj[root]) << '\n';
    return 0;
}

자식노드가 더이상 존재하지 않는경우 리프노드이다 그렇기 때문에 here.size() 가 0인경우 1을 반환해준다. 만약 루트노드를 지우는 경우의 반례를 생각해서 _remove == root 인경우 0을 출력해준다.

 

반례

테스트케이스는 모두 통과했지만 계속 77%에서 틀렸다고 나왔다 무언가 생각하지 못한 반례가 있었다 반례는 다른분의 풀이를 참고하여 해결하였다.

 

루트노드에 단 한개의 자식노드가 존재하고 그 자식노드를 제거했을때 리프노드의 개수를 고려하지 않았던게 문제였다.

지금 코드는 1번 노드를 우선 탐색하려고 하는데 제거노드 인덱스와 일치하기 때문에 아무런 탐색을 하지않고 그대로 함수가 종료된다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
int n, _index, root, _remove;
vector<int> adj[51];

int dfs(vector<int> here){
    if(here.size() == 1 && _remove == here[0]) return 1;
    if(!here.size()) return 1;
    int ret = 0;
    for(int there: here){
        if(there == _remove) continue;
        ret += dfs(adj[there]);
    }
    return ret;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> _index;
        if(_index == -1) {
            root = i; 
            continue;
            }
        adj[_index].push_back(i);
    }
    cin >> _remove;
    if(_remove == root) cout << 0 << '\n';
    else cout << dfs(adj[root]) << '\n';
    return 0;
}

if(here.size() == 1 && _remove == here[0]) return 1 탐색하려는 리프노드의 개수가 1개이면서 제거하는 노드인 경우 1을 반환하도록 반례처리를 해줘야한다.