[BAEKJOON]백준 1068번 트리 - DFS(깊이 우선 탐색)

백준 1068번 트리

백준 1068번 트리

설명

부모노드의 리스트, 지울 노드로 dfs를 호출한다.

지울 노드 값의 부모 리스트를 -2로 바꾸고 부모 리스트를 돌면서 지울노드가 있는지 찾는다.

있으면 지울 노드의 자식 노드들이 있다는 말이기 때문에 그 값을 지울 노드로 해서 dfs를 호출해서 그 값을 -2로 바꿔준다.

이렇게 하면 지울노드와 그 자식노드 모두다 그 위치에 부모노드 리스트에 -2가 박힌다.

그 다음 부모 노드 리스트 인덱스로 쭈욱 돌면서 그 값이 -2가 아니고, 인덱스가 부모리스트에 아에 없는 값이 있으면 count를 1 증가 시키고, count가 정답

인덱스가 부모 리스트에 없으면 그 인덱스를 부모로 가지는 자식이 없다는 말이기 때문에 그 인덱스는 리프노드임

코드

import sys
from typing import List
input = sys.stdin.readline
class Solution:
    def leaf(self, N: int, tree: List[int], k: int):
        def dfs(k, tree):

            """tree리스트에서 지울 노드쪽을 
            의미 없는 -2로 바꿔준다. """
            tree[k] = -2

            for i in range(len(tree)):

                """k를 부모노드로 가지는 
                i(자식노드)를 찾아서 dfs를 호출하면
                자식노드 쭈루룩 다 -2로 바뀌고 dfs 종료됨"""
                if k == tree[i]:
                    dfs(i, tree)

        # 지울 노드와 노드의 부모리스트로 dfs 호출
        dfs(k, tree)


        count = 0

        """이젠 for문으로 tree리스트를 인덱스(트리노드)를 
        기준으로 해서 돌면서 -2면은 지울노드 및 지울노드의 
        자식노드들이므로 다 넘어가고, 트리노드가 트리의 
        값(부모노드)에 없으면 count를 1 증가시킴"""
        for i in range(len(tree)):
            if tree[i] != -2 and i not in tree:
                count += 1
        return count

N = int(input())
tree = list(map(int, input().split()))
k = int(input())
print(Solution().leaf(N, tree, k))