[백준] 1068번 트리 (C++)

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

 

 

이 문제는 트리가 주어졌을때 어느 한 부분을 제거하고 난 후 트리에서 리프노드의 개수를 구하는 문제이다.

 

여기서 알아야 할 점은 리프노드는 자기 자식을 가지지 않는 노드이다.

 

트리 구조이기때문에 dfs를 사용하여 풀어야겠다고 생각을 하였다.

 

 

처음엔 트리가 무조건 이진트리로 들어온다고 생각을 하여 간선이 하나인 경우는 리프 노드라고 생각하여 구현을 했는데

계속 틀렸어서 질문게시판을 확인해보니 무조건 이진트리로 들어오는 것이 아닌 위 그림처럼 들어올 수도 있다고 나와서

다른 방법으로 접근을 하였다.

 

dfs로 호출을 할때 지울 노드 번호를 만났을때 바로 continue를 걸어주어 재귀호출을 못하게 하였으며

함수 내에서 children 변수를 두어 자식이 몇개인지 세주었으며

 

만약 변수가 0인경우 재귀호출을 하지 않았고 이는 리프노드이기 때문에 개수를 늘려주었다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int N, M;
vector<vector<int>> v(51);
bool visited[51];
int start;
int cnt;

void dfs(int Node, int parent) {
    visited[Node] = true;
    int children = 0;

    for(auto it : v[Node]) {
        if(it == M || it == parent) continue;
        children++;
        dfs(it, Node);
    }
    if(children == 0) cnt++;
}

void solve() {
    if(start != M) {
        dfs(start, -1);
    }

    cout << cnt;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;

        if(a != -1) {
            v[i].push_back(a);
            v[a].push_back(i);
        }
        else start = i;
    }

    cin >> M;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}