[파이썬/Python] 백준 1068(🥇5): 트리

숨·2025년 8월 11일

코테

알고리즘 문제 풀이

목록 보기

109/128

📌 문제 : 백준 1068

📌 문제 탐색하기

N : 노드의 개수 ( $1 ≤ N ≤ 50$ )

문제 풀이

트리의 부모-자식 간 정보를 저장하고 입력 받은 삭제 노드와 그 아래 트리들을 모두 삭제한 후 자식이 없는 리프 노드의 개수를 구하는 문제이다.

삭제 노드를 찾으면 그 노드부터 연결된 모든 노드들을 삭제하므로 DFS를 사용하고자 한다.

DFS를 통해 자손 노드들을 모두 찾아 삭제 처리한 후, 모든 노드들을 확인해 자식 유무를 파악하여 리프 노드의 개수를 세고자 한다.

가능한 시간복잡도

DFS(각 노드마다 N번 반복) → $O(N^2)$
리프노드 개수 세기 → $O(N^2)$

최종 시간복잡도
최악일 때 $O(N^2) = O(50^2) = O(2500)$ 이 되는데 이는 제한시간 2초 내 충분히 수행 가능하다.

알고리즘 선택

DFS로 연결된 모든 자손 트리 찾기

📌 코드 설계하기

dfs 구현
입력 받기
dfs 실행
리프노드 개수 저장 변수 초기화
리프노드 개수 세기

📌 시도 회차 수정 사항

1회차

예제 입력3과 4가 제대로 동작하지 않았다.
삭제 노드의 자식은 삭제되었지만 그 자식 노드의 자식 노드가 제대로 삭제되지 않아 발생한 문제였다.

DFS 구현 코드에서 DFS 입력으로 들어간 node의 값에 대해 처리를 해야 하는데 변수를 입력받은 delete_node를 작성해서 삭제 노드와 그 자식 노드까지만 삭제되었다.

# DFS 구현
def dfs(node):
    # 삭제 노드 표현
    parent[node] = 51
    # 부모 노드가 지울 노드 번호와 똑같은 경우 계속 탐색해 삭제 노드로 표현
    for i in range(N):
        if parent[i] == delete_node:
            dfs(i)

📌 정답 코드

import sys

input = sys.stdin.readline


# DFS 구현
def dfs(node):
    # 삭제 노드 표현
    parent[node] = 51
    # 부모 노드가 지울 노드 번호와 똑같은 경우 계속 탐색해 삭제 노드로 표현
    for i in range(N):
        if parent[i] == node:
            dfs(i)


# 입력받기
N = int(input())
parent = list(map(int, input().split()))
delete_node = int(input())

# 노드 삭제
dfs(delete_node)

# 리프 노드 개수 저장 변수 초기화
count = 0

# 리프 노드 개수 세기
for i in range(N):
    # 삭제되지 않은 상태에서 자식 노드가 없다면 리프노드 개수 추가
    if parent[i] != 51 and i not in parent:
        count += 1

# 정답 출력
print(count)