BOJ(백준) 1068[트리]

안녕하세요! 오늘은 백준의 1068번 문제인 “트리” 문제를 함께 풀어보겠습니다. 이 문제는 트리 구조에서 특정 노드를 제거했을 때 남은 트리의 리프 노드의 개수를 구하는 문제입니다.

 

1. 문제 설명

1) 문제 개요

• 주어진 트리에서 특정 노드를 제거하고, 남은 트리의 리프 노드의 개수를 세는 문제입니다.

• 트리의 각 노드는 0부터 N-1까지 번호가 매겨져 있습니다.

• 주어지는 트리의 노드 수 N은 1 이상 50 이하입니다.

 

2) 입력

• 첫 줄에 트리의 노드 수 N이 주어집니다.

• 두 번째 줄에 각 노드의 부모 노드를 나타내는 N개의 정수가 주어집니다. 부모 노드가 없는 경우에는 -1이 주어집니다.

• 세 번째 줄에 제거할 노드의 번호가 주어집니다.

 

3) 출력

• 제거된 노드를 제외한 나머지 트리에서 리프 노드의 개수를 출력합니다.

 

문제 URL: https://www.acmicpc.net/problem/1068

 

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 N(노드의 수)을 입력받고, 두 번째 줄에서 각 노드의 부모 노드를 입력받습니다.

• 세 번째 줄에서 제거할 노드의 번호를 입력받습니다.

 

2) 트리 구조 이해 및 제거된 노드 표시

• 트리의 루트 노드를 찾습니다 (부모가 -1인 노드).

• 제거된 노드와 그 자식 노드를 표시하기 위해 rNode 배열을 사용합니다.

• 제거된 노드의 부모 노드도 고려하여 리프 노드 여부를 판단하기 위해 pNode 배열을 사용합니다.

 

3) 리프 노드 개수 계산

• 제거된 노드와 그 자식 노드를 제외하고, 리프 노드를 계산합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# 입력 받기
N = int(input())                            # 노드의 수
parent = list(map(int, input().split()))    # 각 노드의 부모 노드
rmv = int(input())                          # 제거할 노드의 번호

# 루트 노드 찾기
root = -1
for i in range(N):
    if parent[i] == -1:  # 부모가 -1인 노드가 루트 노드
        root = i
        break

# rNode 배열을 사용하여 제거된 노드와 그 자식 노드를 표시
rNode = [0] * N
for i in range(N):
    u = i
    while True:
        if u == rmv:        # 현재 노드가 제거된 노드와 같으면
            rNode[i] = 1    # 제거된 노드로 표시
            break
        if u == root:       # 루트 노드에 도달하면 PASS
            break
        u = parent[u]       # 부모 노드로 이동

# pNode 배열을 사용하여 부모가 제거되지 않은 노드를 표시
pNode = [0] * N
for i in range(N):
    if i == root:           # 루트 노드는 제외
        continue
    if rNode[i] == 1:       # 제거된 노드는 제외
        continue
    pNode[parent[i]] = 1    # 부모 노드를 표시

# 리프 노드의 개수를 세기
ans = 0
for i in range(N):
    if rNode[i] != 1 and pNode[i] != 1: # 제거된 노드가 아니고 부모가 아닌 노드
        ans += 1                        # 리프 노드로 간주하고 개수를 증가

print(ans)  # 리프 노드의 수를 출력

 

4. 코드 설명

[1]

예제

5

-1 0 0 1 1

2

 

입력 설명

 

• 노드 수 N = 5

• 부모 노드 배열 parent = [-1, 0, 0, 1, 1]

• 노드 0은 루트 노드 (부모가 -1)

• 노드 1과 2는 노드 0의 자식

• 노드 3과 4는 노드 1의 자식

• 제거할 노드 rmv = 2

 

트리 구조

      0

     / \

    1   2

   / \

  3   4

 

제거할 노드 2

 

• 노드 2를 제거하면 다음과 같은 트리가 됩니다

      0

     /

    1

   / \

  3   4

 

이 코드를 실행하면 제거된 노드를 고려한 리프 노드의 개수를 출력합니다. 주어진 예제에서는 노드 2가 제거되었으므로, 남은 트리에서 리프 노드는 3번과 4번 두 개입니다.

 

[2]

다음은 위 코드의 각 단계별 작업을 순서도로 나타낸 것입니다:

 

1. 입력 받기

• 노드 수 N, 부모 노드 배열 parent, 제거할 노드 rmv를 입력받습니다.

2. 루트 노드 찾기

• 부모 노드가 -1인 노드를 루트 노드로 설정합니다.

3. 제거된 노드와 자식 노드 표시

• 제거된 노드와 그 자식 노드를 표시합니다.

4. 부모 노드 표시

• 부모가 제거되지 않은 노드를 표시합니다.

5. 리프 노드 개수 세기

• 제거된 노드가 아니고 부모 노드도 아닌 노드를 리프 노드로 간주하여 개수를 셉니다.

6. 출력

• 리프 노드의 수를 출력합니다.

 

5. Github으로 확인

 

coTest/BOJ/BOJ01_06_04_1068.py at main · pcy4196/coTest