[백준 1068] 트리

문제

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

1068번: 트리

 

 

문제 분석 

노드의 개수가 입력 되고 그 개수에 맞춰 부모 노드가 누구인지 정해준다. 

 

이후 없앨 노드가 입력되고 없앤 상태의 트리에서 리프노드가 몇개인지 세는 문제이다. 

 

 

알고리즘 설계 

이중 vector을 사용하여 간단한 트리를 만들어준다. 

 

루트 노드에서 DFS를 돌린다. 

 

DFS에 매개변수로 들어간 수가 지운 노드라면 return해준다. 

 

만약 자식 노드가 없거나, 자식이 하나인데 그 자식이 지워진 노드라면 리프노드의 개수를 하나 늘려준다. 

 

이후 매개변수로 들어온 노드의 하위 노드를 DFS돌려준다. 

 

 

유의점 

지워지는 노드가 이중vector에서는 지워지지 않기에 그 부분을 잘 생각하여 작성하여야 한다.

 

 

코드 

#include <iostream>
#include <vector>

using namespace std;

int cnt = 0, input;
vector<vector<int>> graph;
vector<bool> visited;

void DFS(int i);

int main()
{
    int index;
    vector<bool> rootNode;
    cin >> index;
    graph.resize(index);
    visited.resize(index, false);
    rootNode.resize(index, false);

    for (int i = 0; i < index; ++i)
    {
        cin >> input;
        if (input == -1)
            rootNode[i] = true;
        else
            graph[input].push_back(i);
    }

    cin >> input;

    for (int i = 0; i < rootNode.size(); ++i)
    {
        if (rootNode[i])
            DFS(i);
    }

    cout << cnt;
}

void DFS(int i)
{
    if (i == input)
    {
        return;
    }

    if ((i != -1 && graph[i].size() == 0) || (graph[i].size() == 1 && graph[i][0] == input))
    {
        ++cnt;
        return;
    }

    for (int idx : graph[i])
    {
        if (visited[idx])
            continue;

        visited[i] = true;
        DFS(idx);
    }
}