[백준] 트리

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

분류:: dfs, 트리

 

1. 문제 이해 및 해결과정

 

2. 풀이방법

  1. [ python ] 딕셔너리 이용

#트리
#https://www.acmicpc.net/problem/1068
import sys
from collections import deque
sys.stdin = open("input.txt","r")
n=int(input()) #노드의 개수
tree={}
parents=list(map(int,input().split())) #각 노드의 부모노드가 주어진다
d=int(input()) #삭제할 노드 
for i in range(n): #트리의 형태 만들어 줌
    tree[i]=[] #{0: [], 1: [], 2: [], 3: [], 4: []} 부모: 자식

for i, p in enumerate(parents):
    if p==-1: #루트노드
        continue
    else:
        tree[p].append(i)
#tree : {0: [1, 2], 1: [3, 4], 2: [], 3: [], 4: []}

if parents[d]!=-1:#삭제할 노드가 루트노드가 아니면
    tree[parents[d]].remove(d) #부모노드의 d번 자식 삭제

q = deque()
q.append(d) #삭제할 노드
print(tree)
#삭제할 노드가 리프노드가 아니면 자식들도 삭제해야함
while q:
    print(q)
    i = q.popleft()

    if i in tree:
        for j in tree[i]:
            q.append(j) #i의 자식도 삭제가 되므로
        del tree[i] #i삭제
print(tree)
print(len(list(filter(lambda child: len(child) == 0, tree.values()))))
#리스트의 내장함수 filter
#filter(function,iterable) -> 조건, 리스트/값

  2.  [python] 1번과 같은 코드

#트리
#https://www.acmicpc.net/problem/1068
import sys
from collections import deque
sys.stdin = open("input.txt","r")
n=int(input()) #노드의 개수
tree={} #트리를 만들어 주자
parents=list(map(int,input().split())) #각 노드의 부모노드가 주어진다
d=int(input()) #삭제할 노드
#1. 트리의 틀을 만든다
for i in range(n):
    tree[i]=[]
#2.입력받은 부모대로 트리를 그려준다
for i in range(n):
    if parents[i]!=-1: #루트노드가 아니라면
        tree[parents[i]].append(i)
    else: #루트노드면
        continue
print(tree)
#삭제할 노드가 리프노드라면 삭제해준다
if parents[d]!=-1:
    tree[parents[d]].remove(d)
# print(tree)
#삭제할 노드가 리프노드가 아니라면
q=deque()
q.append(d)
while q:
    node=q.popleft()
    if node in tree:#트리의 부모노드로 있다면
        for leaf in tree[node]:
            q.append(leaf)
        del tree[node] #자식노드 제거 완료 후, 부모노드 제거 

print(len(list(filter(lambda child:len(child)==0,tree.values()))))

  3. [ python ] dfs

#트리
#https://www.acmicpc.net/problem/1068
import sys
from collections import deque
sys.stdin = open("input.txt","r")
n=int(input()) #노드의 개수
tree=[[] for _ in range(n)] #트리를 만들어 주자
parents=list(map(int,input().split())) #각 노드의 부모노드가 주어진다
d=int(input()) #삭제할 노드
def dfs(root): #리프노드의 개수를 구하는 함수
    global cnt
    if len(tree[root])==0: #리프노드라면
        cnt+=1
    else: #리프노드가 아니라면 가지를 타고 들어가야함
        for x in tree[root]:
            dfs(x)

#1. 트리 그리기
for i in range(n):
    if parents[i]==-1:
        root=i #루트노드라면
    else:
        tree[parents[i]].append(i)
print(tree)
#2. 삭제할 노드가 리프노드일 경우, 삭제
for i in range(n):
    if d in tree[i]:
        tree[i].remove(d)
print(tree)
#3.삭제할 노드가 리프노드가 아닐경우
cnt=0 #리프노드의 개수
if d!=root:
    dfs(root)  #루트노드에서 시작
print(cnt) #루트노드를 지우면 0이 됨

 

 

3. 오답원인

 

4. 알게된 점

리스트의 내장함수, filter

- filter(function,iterable)

- list.filter()로 쓰지 않고 list(filter(조건(함수), 값(리스트)))이렇게씀

- 값(리스트) 중에 조건(함수)를 만족하는 것을 필터링한다