관리 메뉴

Mini

백준 1068 // 2차원벡터선언법 / 트리문제는 root 1개만 남는상황 예외처리하라 / 리프노드 카운팅은 int dfs 본문

Algorithm/boj

백준 1068 // 2차원벡터선언법 / 트리문제는 root 1개만 남는상황 예외처리하라 / 리프노드 카운팅은 int dfs

Mini_96 2023. 5. 23. 00:23

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

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다

www.acmicpc.net

* 2차원벡터선언법

vector<int> adj[54];

* 극단적예외처리

0-1 트리에서, 1이 삭제되는경우 //정답 : 1이 나와야함(root가 리프노드)

모든인접노드에대해, 인접노드가 삭제예정이 아닐때만 자식으로인정.

if(i!=del) child++;

 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int root, n, t, del, v[54];
//vector<vector<int>> adj(104,vector<int>(104,0));    //(크기,초기화대상)
vector<int> adj[54];
int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };

int dfs(int here)
{
    v[here] = 1;    //방문처리를 먼저하라.
    if (here == del) { return 0; }

    int child = 0;
    int ret = 0;
    for (int i : adj[here])
    {
        if (v[i]) continue;
        if(i!=del) child++;
        ret += dfs(i);
    }
    if (child == 0) return 1;

    return ret;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> t;
        if (t == -1) { root = i; continue; }
        adj[t].push_back(i);
    }
    cin >> del;
    if (del == root) {
        cout << 0 << "\n"; return 0;
    }
    cout << dfs(root);

    return 0;
}