백준 1068번: 트리

BOJ

백준 1068번: 트리

접근

노드 간의 연결을 알 수 있는 인접행렬을 만들어준다. 제거할 노드를 입력받는다. 제거할 노드와 연결된 간선들을 지워준다. dfs를 진행해서 다음으로 갈 노드가 없으면 cnt에 1을 더해준다.

Correct Solution 1

import sys
input = sys.stdin.readline

def dfs(node, arr):
    arr[node] = -2

    for i in range(len(arr)):
        if node == arr[i]:
            dfs(i, arr)

N = int(input())
tree = list(map(int, input().split()))
K = int(input())

dfs(K, tree)

cnt = 0
for i in range(len(tree)):
    if tree[i] != -2 and i not in tree:
        cnt += 1
print(cnt)

Correct Solution 2

import sys
input = sys.stdin.readline

def dfs(node):
    global answer

    if not tree[node]:
        answer += 1
        return

    for j in tree[node]:
        dfs(j)

N = int(input())
arr = list(map(int, input().split()))
tree = [[] for _ in range(N)]
K = int(input())

root = 0
for i in range(N):
    if arr[i] == -1:
        root = i
        continue
    if i == K or arr[i] == K:
        continue
    tree[arr[i]].append(i)

answer = 0
if root != K:
    dfs(root)
print(answer)

참고 사이트

식용감자네

지혜로운 개발로그