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

문제링크 : https://www.acmicpc.net/problem/1068

1068번: 트리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, remove_node, root, result;
vector<int>t[51]; //트리
int visited[51]; //방문처리용 

void dfs(int node)
{
    visited[node]=1;
    bool flag = 1; //리프노드 체크용
    for(int i=0; i<t[node].size(); i++)
    {
        if(visited[t[node][i]] || t[node][i]==remove_node) continue; //다음값이 없으면 패스
        flag = 0;
        dfs(t[node][i]); //다음값 이어서 탐색 
    }
    if(flag) result++; //dfs탐색을 하지 못했다는 것이므로 (리프노드 O) 카운트
}

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

    cin >> N;
    for(int i=0; i<N; i++)
    {
        int n;
        cin >> n;
        if(n==-1) root = i; //루트 표시
        else t[n].push_back(i);
    }

    cin >> remove_node;
    dfs(root);
    cout << (root == remove_node ? 0 : result); //루트랑 삭제노드랑 같다면 전부 삭제이므로 0 출력
    
}

트리와 관련한 문제이다.

입력할때 루트(-1)인 경우의 인덱스를 따로 저장해두어야 한다.

 

기본적으로 dfs 탐색을 이용해 다음 값을 탐색해나간다.

먼저 현재 노드와 인접한 노드가 있는지를 확인한다.

인접한 노드가 있는 경우는 현재 노드가 리프노드가 아니라는 뜻이므로 이어서 탐색을 한다.

 

인접한 노드가 있더라도 해당 값이 삭제된 노드 (remove_node)라면 현재 노드가 리프노드가 된다.

인접한 노드를 이미 방문했다면 부모->자식에서 자식->부모로 가는 경우와 같이 새로운 다음 값이 아닌,

이미 방문했던 기존 값을 다시 찾게되는 것이므로 현재 노드가 리프노드라는 것을 알 수 있다.

위 2가지의 경우에 dfs탐색을 스킵하도록 하고, dfs 탐색을 스킵한 경우에 리프노드 체크용 변수 flag는 처음 초기화한 1 그대로일 것이다.

따라서 flag가 1일 때 결과값을 카운팅하고 이를 출력해주면 된다.

 

출력할때는 처음 저장했던 루트의 인덱스가 삭제한 인덱스와 같을 때는 모든 노드가 삭제되는 경우이므로 0을 출력하도록 예외처리를 해주어야한다.