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

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

1068번: 트리

이 문제에서 구현해야할 것은 크게 2가지.

 

1. 지운 노드의 아래 자식 노드 전부 삭제.

 

2. 자식노드 판별 여부

 

이 문제를 처음 접할 때는

트리를 전부 구현해서 푸는 건가...

하고 생각이 들었습니다.

그래서 열심히 파이썬에서 트리를 구현한 걸 찾아봤으나

이 문제에 적용하기는 힘들었습니다.

그러다가, 이 문제의 힌트를 얻으면서

차근히 풀었습니다.

 

1. dfs를 이용해서 자식노드를 지운다.

위의 문제처럼 2를 지웠다면,

부모노드가 2인 노드를 지워주면 됩니다.

저는 초반에 arr이라는 리스트에

부모노드를 다 받았습니다.

2가 지워졌다면 2를 루트로 삼은 노드는 전부 삭제.

만약 그 노드의 리프가 있다면

dfs로 찾아가서 삭제

 

2. 리프인지 아닌지 판단하는 방법은

먼저, 지워졌는지 확인합니다.

저는 지울 때 -2를 대입해줬습니다.

그 다음은 해당 숫자가 arr에 있는지입니다.

만약에 예시처럼 2를 지웠다면

arr에는 2가 존재할 수 없습니다.

 

#백준 1068번 트리

N=int(input())

arr=list(map(int,input().split()))

erase=int(input())

#dfs해주면서 지움
def dfs(index):
    arr[index]=-2
    for i in range(N):
        if arr[i]==index:
            dfs(i)

dfs(erase)
answer=0

#리프인지 확인하는 방법
for i in range(N):
    if not arr[i]==-2 and i not in arr:
        answer+=1

print(answer)

 

dfs에 대한 관점과 함께

트리 구조에 대해서 공부할 수 있었던 문제였습니다.