[BOJ/Python] 1068번: 트리

문제

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

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

입력

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

출력

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

 

아이디어

처음엔 트리 문제라 노드 클래스를 활용해야겠다는 생각으로 열심히 클래스를 짜고 insert문을 작성했는데 

사실 dfs 문제 였던 것

 

일단 트리 가 나오면 트리탐색 문제인지, 트리순회 문제인지 구분해서 생각해보자

보통 트리탐색은 bfs, dfs를 이용하고, 트리순회는 노드 클래스를 이용한단다...

탐색과 순회는 먼 차이인지.......

그래도 하다보면 문제보는 눈이 생길거라는 믿음으로 🤣

 

해결방안

import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int,input().split()))
idx = int(input())
cnt = 0

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

delete(idx)

for i in range(n):
    if nums[i] != -2 and i not in nums:
        cnt+=1

print(cnt)

 

처음엔 열심히 graph를 만들고 visited 배열 만들었는데 그것도 필요없다.

따지자면 각 원소가 자기 부모노드의 값을 가진 꼴이므로 주어진 노드의 값 (배열의 인덱스 값과 같음) 을 -2로 바꾸고 그 노드에 자식이 있다면 재귀를 활용해서 전부 -2 바꾼다

 

그렇게 되면 배열에 존재하지 않는 노드들은 전부 -2로 바뀌고

 

마지막에 배열을 돌면서 -2가 아니고 자식이 없는 리프노드일 때만 cnt += 1 을 하여 리프노드의 개수를 구할 수 있다.