boj.kr/1068 트리 (gold5) 파이썬 풀이

graph 를 하나 더 생성해 풀이하여 테스트 케이스 통과했으나 제출 시 실패했다.

N = int(input())
parents = list(map(int, input().split()))
delete = int(input())

graph = [[] for _ in range(N)]
for i in range(1, N):
    graph[parents[i]].append(i)


leaf_cnt = 0
def dfs(node):
    global leaf_cnt
    for child in graph[node]:
        if len(graph[child]) > 0:
            dfs(child)
        else:
            leaf_cnt +=1

dfs(0)
leaf_cnt_0 = leaf_cnt

leaf_cnt = 0
dfs(delete)

if delete == 0:
    leaf_cnt = 0
elif len(graph[delete]) > 0:
    leaf_cnt = leaf_cnt_0 - leaf_cnt
elif len(graph[delete]) == 0:
    if parents.count(parents[delete]) == 1:
        leaf_cnt = leaf_cnt_0
    else:
        leaf_cnt = leaf_cnt_0 - 1

print(leaf_cnt)

 

정답 풀이

1. 삭제되는 노드 하위의 모든 노드를 삭제 처리하기 위한 dfs를 다음과 같이 정의

1.1.  삭제되는 노드번호를 인자로 전달

1.2. 전달받은 삭제되는 노드 번호를 인덱스로 갖는 tree 의 요소값을 -2으로 갱신

1.3. 0번부터 마지막 노드 i 까지 순회하면서 tree[i] 값이 삭제되는 노드 번호이면, dfs(i)를 호출

2. dfs(삭제되는노드번호) 호출

3. cnt 변수를 0으로 초기화

4. 0번째 노드부터 마지막 노드 j까지 순회하면서 tree[j]가 -2(삭제된 노드)가 아니고 j가 tree에 없으면(자식노드가 없으면)

cnt를 1씩 증감

5. cnt값을 출력

N = int(input())
tree = list(map(int, input().split()))
delete = int(input())
import sys
sys.setrecursionlimit(10**9)
def dfs(parent):
    tree[parent] = -2
    for i in range(N):
        if tree[i] == parent:
            dfs(i)
dfs(delete)
cnt = 0
for j in range(N):
    if tree[j] != -2 and j not in tree:
        cnt += 1
print(cnt)

삭제되는 노드와 그 자식 노드들을 모두 표시하고 해당 제외한 리프 노드들을 카운트 할 수 있다.

 

 

참고출처

"[DFS] 백준 1068번 “트리” Python 풀이", wooono.tistory.com, 2022년 11월 31일 수정, 2023년 6월 21일 접속, https://wooono.tistory.com/636.