[baekjoon] 백준 1068번(파이썬): 트리

문제

1068번: 트리

알고리즘

- dfs 탐색을 통해 문제를 수행한다.

- 제거할 노드를 정의한다.

- 제거할 노드와 연결되어있는 리프 노드를 재귀함수를 통해 다시 제거할 노드를 찾는다.

- 반복문을 통해 제거할 노드가 아니고 리프 노드가 없다면 카운트한다.

코드

import sys
sys.setrecursionlimit(10 ** 6)


# dfs 탐색
def dfs(delete):
    # 제거할 노드를 -2로 정의
    tree[delete] = -2

    # 반복문을 통해 제거할 노드의 리프노드를 확인
    for i in range(n):
        if delete == tree[i]:
            # 제거할 리프 노드의 리프 노드를 재귀적으로 탐색
            dfs(i)


n = int(sys.stdin.readline())
tree = list(map(int, sys.stdin.readline().split()))
d = int(sys.stdin.readline())
cnt = 0

# 노드를 삭제
dfs(d)

# 반복문을 통해 제거할 노드가 아니고 트리에 해당 노드의 리프 노드가 없다면 카운트
for i in range(n):
    if tree[i] != -2 and i not in tree:
        cnt += 1

print(cnt)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법