[Python] 백준 1065 트리

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

1068번: 트리

문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

이제 리프 노드의 개수는 1개이다.

 

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

 

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

 

예제 입력 1 

5
-1 0 0 1 1
2

예제 출력 1

2

코드 및 설명

import sys
input=sys.stdin.readline

n=int(input())

result=[[] for _ in range(n)]
node=list(map(int,input().split()))

x=int(input())
for i in range(n):
    result[i]=node[i]

def delete(x):
    result[x]=-2
    for i in range(n):
        if result[i]==x:
            result[i]=-2
            delete(i)

delete(x)
cnt=0

for i in range(n):
    if result[i]!=-2:
        err=0
        for j in result:
            if j==i:
                err=1
        if err==0:
            cnt +=1
print(cnt)

이 문제는 트리 관련 연습 문제를 찾다가 발견하게 된 문제

트리에 대한 개념 이해도 부족했겠지만 골드 단계이기에 좀 더 어렵게 느껴졌다.

 

코드에 대해서 설명해보겠다.

일단 입력 과정에서 짚어야 할 것은 리스트 내에서 반복문을 통한 2중 리스트 만들기

이걸 처음에 방법을 잘 몰라서 []*n 이런 방식으로 했는데 이런 경우에는 빈 리스트가 생성되지 않았다.

그래서 이렇게 [[] for _ in range(n)]방식으로 생성을 시켜주어야 한다.

노드와 리프 노드 찾는 입력 생성은 어렵지 않으니 넘어가도록 하겠다.

 

그리고 앞에서 생성한 리스트에 입력받은 리스트를 넣어주었다.

 

함수를 한번 살펴보자면

리프 노드를 찾는 위치는 -2로 설정해서 다른 숫자와 겹쳐지지 않게 한다.

그리고 모든 result의 요소를 탐색해 찾고자 하는 위치라면 노드가 연결되어 있으므로 -2로 값을 바꿔주고 다시 그 위치에 대해 호출해준다.

 

그리고 출력을 위한 작업을살펴보도록 하자

일단 -2가 아니라면 진입하도록 하는데, 기본 세팅을 0으로 하고 result의 값을 비교한다.

만약 result의 요소와 같은 숫자가 i에서 나오게 되면 리프노드가 삭제된 사건이므로 err를 1로 해준다.

err가 0으로 그대로라면 리프노드이므로 갯수를 카운트 해준다.

그리고 이 결과값을 최종적으로 출력해주면 된다.

 

트리에 대해 어떻게 구성해야 하는지 생각하게 해주는 문제였다.