[파이썬] 백준 1068 : 트리 (골드5)

[파이썬] 백준 1068 : 트리 (골드5)

1068번: 트리

---

문제

---

풀이

0. 방향성 생각

• 각 노드에서 하위 리프노드가 몇 개인지 기록하기

1. 입력

import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
tree_info = list(map(int, input().split()))
remove = int(input())

leaf = [0]*n
tree = [[] for _ in range(n)]
for idx,x in enumerate(tree_info):
    if x != -1: tree[x].append(idx)
    else: start = idx

• tree_info를 받아서 tree 형태로 저장
• leaf 에는 각 노드가 몇 개 리프노드를 가지는지 저장

2. DFS 함수 정의

def dfs(x):    
    cnt = 0
    if tree[x]:
        for nx in tree[x]:
            cnt += dfs(nx)
        leaf[x] = cnt
        return cnt
    else:
        leaf[x] = cnt
        return 1

• DFS를 통해서 리프노드에는 0, 상위 노드에는 리프 노드 개수를 저장해준다.

3. 출력

dfs(start)
answer = leaf[start]
if remove == start:
    answer -= answer
    
elif leaf[remove]:
    answer -= leaf[remove]
    if len(tree[tree_info[remove]]) == 1:
        answer += 1

elif not leaf[remove]:
    answer -= 1
    if len(tree[tree_info[remove]]) == 1:
        answer += 1
print(answer)

• 엣지케이스(?)가 존재. 내가 모르면 엣지케이스임..
• 0 1 2 3이 일렬로 나열돼있는 경우 1 2 3을 제거해도 리프노드가 1개로 동일하다.
• remove node를 결정했을 때 remove node의 부모노드가 자식을 1개, 혹은 그 이상 가지고 있는지가 중요하다.
• 또한 리프노드를 제거하는지, 리프노드가 아닌 노드를 제거하는지도 중요하다.
• 루트노드 제거하는 경우, 리프노드인 경우, 리프노드가 아닌 경우로 구분.
• 루트가 아닌경우에는, 제거하는 노드에 기록된 리프노드 개수만큼 제거해준다.
• 제거했는데 부모노드가 리프노드가 되는 경우 (remove node의 부모노드가 자식이 1개인 경우) 부모노드가 리프노드가 되버리므로 +1 해주기.

 

---

전체코드

import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
tree_info = list(map(int, input().split()))
remove = int(input())

leaf = [0]*n
tree = [[] for _ in range(n)]
for idx,x in enumerate(tree_info):
    if x != -1: tree[x].append(idx)
    else: start = idx

def dfs(x):    
    cnt = 0
    if tree[x]:
        for nx in tree[x]:
            cnt += dfs(nx)
        leaf[x] = cnt
        return cnt
    else:
        leaf[x] = cnt
        return 1

dfs(start)
answer = leaf[start]
if remove == start:
    answer -= answer
    
elif leaf[remove]:
    answer -= leaf[remove]
    if len(tree[tree_info[remove]]) == 1:
        answer += 1

elif not leaf[remove]:
    answer -= 1
    if len(tree[tree_info[remove]]) == 1:
        answer += 1
print(answer)

 

코멘트