[백준] 1068 - 트리

1. 문제

1068번: 트리

2. 개요

트리 노드의 총 갯수 N과 각 노드의 부모의 번호들이 주어진다.

또한 지울 노드의 번호가 주어지는데, 노드를 지우면 그 노드와 모든 자손들이 같이 지워진다.

이 때, 트리의 모든 리프 노드의 갯수를 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 입력을 받아 트리를 만들어준다.

이 때 꼭 0번 노드가 루트 노드라는 보장이 없기 때문에 -1을 부모로 갖는 노드를 루트로 갱신한다.

또한 삭제될 노드거나 삭제될 노드를 부모로 갖는 경우에는 패스한다.

만약 삭제될 노드가 루트 노드라면 바로 0을 출력하고 끝낸다.

그렇지 않다면 만들어진 트리를 루트 노드부터 DFS로 순회, 자식이 없다면 answer를 +1씩 늘린다.

순회가 끝났다면 answer를 출력한다.

3-2. Python

import sys
N = int(sys.stdin.readline())

answer = 0
root = 0
parents = list(map(int, sys.stdin.readline().split()))
tree = [[] for i in range(N)]

deleted = int(sys.stdin.readline())

for i in range(N):
    if parents[i] == -1:
        root = i
        continue

    if i == deleted or parents[i] == deleted:
        continue
    
    tree[parents[i]].append(i)

if deleted == root:
    print(0)
    sys.exit()

def DFS(childrens):
    global answer
    if len(childrens) == 0:
        answer += 1

    else:
        for child in childrens:
            DFS(tree[child])

DFS(tree[root])
print(answer)

3-3. C#

namespace boj_1068
{
    internal class Program
    {
        static List<List<int>> tree;
        static int answer = 0;
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int root = 0;
            int[] parents = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int deleted = int.Parse(Console.ReadLine());

            tree = new List<List<int>>();
            for (int i = 0; i < N; i++)
                tree.Add(new List<int>());

            for (int i = 0; i < N; i++)
            {
                if (parents[i] == -1)
                {
                    root = i;
                    continue;
                }

                if (i == deleted || parents[i] == deleted)
                    continue;

                tree[parents[i]].Add(i);
            }

            if (deleted == root)
                Console.WriteLine(0);

            else
            {
                DFS(tree[root]);
                Console.WriteLine(answer);
            }
        }

        static void DFS(List<int> children)
        {
            if (children.Count == 0)
                answer++;

            else
            {
                foreach (int child in children)
                    DFS(tree[child]);
            }
        }
    }
}