본문 바로가기
Computer Science/Baekjoon

[Baekjoon] 1068번 트리 G5

seungjoonH 2024. 1. 15. 23:17
728x90

1068번 - 트리

1. 문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
예를 들어, 다음과 같은 트리가 있다고 하자.

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

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

  • Input

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

  • Output

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

2. 사용 데이터 구조 및 알고리즘

2.1. 데이터 구조

  • 트리 (Math)

2.2. 알고리즘

3. 풀이

본 문제의 풀이를 다음의 두 단계로 진행하도록 한다.

  1. 트리에서 특정 노드틀 삭제한다.
  2. 트리의 말단 노드의 개수를 센다.

문제를 해결함에 있어 편의를 위해 위 문제에서 제시된 예시보다 다소 복잡한 예시와 함께 설명하고자 한다.

3.1. 예시

임의의 트리는 다음과 같다.

이 트리의 노드 9 를 삭제하고자 한다면, 다음과 같은 입력값을 갖는다.

13
4 4 1 1 10 6 9 0 9 10 -1 6 8
9

위 이미지 트리의 빨간색 노드를 삭제하면, 주황색 부분의 서브 트리 역시 삭제된다.

최종적으로 위와 같은 형태의 트리가 남게되며, 말단 노드는 노드 3, 노드 2, 노드 7 의 세 개가 남는다.

따라서 정답은 $3$ 이다.

3.2. 서브 트리 삭제

한편, 서브 트리를 삭제함에 있어 너비 우선 탐색 (BFS) 또는 깊이 우선 탐색 (DFS) 의 알고리즘을 사용할 수 있다.

3.2.1. 너비 우선 탐색 사용

너비를 우선으로 서브 트리를 탐색할 경우,

노드 9 를 필두로 노드 6, 노드 8, 노드 12, 노드 5, 노드 11 를 순서대로 삭제할 수 있다.

3.2.1. 깊이 우선 탐색 사용

깊이를 우선으로 서브 트리를 탐색할 경우,

노드 9 를 필두로 노드 8, 노드 12, 노드 6, 노드 5, 노드 11 를 순서대로 삭제할 수 있다.

4. 구현

4.1. 값 입력 부분

input()
tree = dict(enumerate(map(int, input().split())))
remove = int(input())

둘째 줄과 셋째 줄의 입력값을 담을 변수를 tree, remove 로 나타내었다.

사실상 Python 언어에서 첫째 줄의 사용은 불필요하기 때문에, input() 로 무시할 수 있다.

둘째 줄의 경우, tree 에 할당되는 dict 의 Key 와 Value 는 다음과 같다.

Key: 각 노드의 번호
Value: 각 노드의 부모 노드 번호

위 예시의 입력값에 따라 tree 는 다음의 값을 갖는다.

{0: 4, 1: 4, 2: 1, 3: 1, 4: 10, 5: 6, 6: 9, 7: 0, 8: 9, 9: 10, 10: -1, 11: 6, 12: 8}

셋째 줄의 삭제할 노드의 번호를 입력받기 위해 remove = int(input()) 와 같이 구현하였다.

4.2. remove_node() 구현

트리에서 특정 노드를 삭제하는 작업을 수행하는 함수 remove_node() 를 구현한다. 해당 함수는 다음의 매개변수와 반환값을 갖는다.

  • 매개변수: tree(트리), remove(삭제할 노드의 번호)
  • 반환값: 삭제된 트리

4.2.1. 너비 우선 탐색 구현

remove_node() 함수를 너비 우선 탐색 으로 구현해보자.

from collections import deque

# BFS 구현
def remove_node(tree, remove):
  # tree를 깊은 복사한 removed_tree 선언
  # (그냥 tree 사용 시 반복문에서 문제 발생)
  removed_tree = dict(tree)

  # 트리에서 remove 를 삭제
  removed_tree.pop(remove)

  # 삭제한 노드의 번호를 담은 큐를 생성
  queue = deque([remove])

  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 pop 한 값을 parent 에 할당
    parent = queue.popleft()

    # 트리를 탐색
    for node in tree:
      # parent 값을 부모 노드로 하는 노드 판별
      if tree[node] == parent:

        # 트리에서 해당 노드를 삭제
        removed_tree.pop(node)

        # 큐에 해당 노드를 삽입
        queue.append(node)

  # 삭제된 트리 반환
  return removed_tree

위 코드에서는 deque 로 구현한 데이터 구조 Queue 를 사용하여 너비 우선 탐색 알고리즘을 구현하였다.

from collections import deque

def remove_node(tree, remove):
  removed_tree = dict(tree)
  removed_tree.pop(remove)
  print(remove, end=' -> ')

  queue = deque([remove])

  while queue:
    parent = queue.popleft()

    for node in tree:
      if tree[node] == parent:
        removed_tree.pop(node)
        print(node, end=' -> ')

        queue.append(node)

  return removed_tree

tree = dict(enumerate(map(int, input().split())))
remove = int(input())

print(f'INPUT:\n{tree}\n')
print('Removing:', end=' ')
tree = remove_node(tree, remove)
print('FIN\n')
print(f'OUTPUT:\n{tree}')

위와 같이 디버깅 출력문을 활용하면 노드가 삭제되는 순서를 확인할 수 있다.

입력

4 4 1 1 10 8 9 0 9 10 -1 8 6
9

출력

INPUT:
{0: 4, 1: 4, 2: 1, 3: 1, 4: 10, 5: 8, 6: 9, 7: 0, 8: 9, 9: 10, 10: -1, 11: 8, 12: 6}

Removing: 9 -> 6 -> 8 -> 12 -> 5 -> 11 -> FIN

OUTPUT:
{0: 4, 1: 4, 2: 1, 3: 1, 4: 10, 7: 0, 10: -1}

이미지

4.2.2. 깊이 우선 탐색 구현

# DFS 구현
def remove_node(tree, remove):
  # tree를 깊은 복사한 removed_tree 선언
  # (그냥 tree 사용 시 반복문에서 문제 발생)
  removed_tree = dict(tree)

  # 트리에서 remove 를 삭제
  removed_tree.pop(remove)

  # 트리를 탐색
  for node, parent in removed_tree.items():

    # 삭제된 노드를 부모 노드로 하는 노드 판별
    if parent == remove:

      # 해당 노드를 전달하여 재귀 호출
      # 그 반환값을 removed_tree 에 할당
      removed_tree = remove_node(removed_tree, node)

  # 삭제된 트리 반환
  return removed_tree

위 코드에서는 재귀함수 를 이용하여 깊이 우선 탐색 알고리즘을 구현하였다.

def remove_node(tree, remove):
  removed_tree = dict(tree)
  removed_tree.pop(remove)
  print(remove, end=' -> ')

  for node, parent in removed_tree.items():
    if parent == remove:
      removed_tree = remove_node(removed_tree, node)

  return removed_tree

tree = dict(enumerate(map(int, input().split())))
remove = int(input())

print(f'INPUT:\n{tree}\n')
print('Removing:', end=' ')
tree = remove_node(tree, remove)
print('FIN\n')
print(f'OUTPUT:\n{tree}')

위와 같이 디버깅 출력문을 활용하면 노드가 삭제되는 순서를 확인할 수 있다.

입력

4 4 1 1 10 8 9 0 9 10 -1 8 6
9

출력

INPUT:
{0: 4, 1: 4, 2: 1, 3: 1, 4: 10, 5: 8, 6: 9, 7: 0, 8: 9, 9: 10, 10: -1, 11: 8, 12: 6}

Removing: 9 -> 6 -> 12 -> 8 -> 5 -> 11 -> FIN

OUTPUT:
{0: 4, 1: 4, 2: 1, 3: 1, 4: 10, 7: 0, 10: -1}

이미지

4.3. count_leaves() 구현

이제 말단 노드의 개수를 세는 함수 count_leaves() 를 구현한다. 해당 함수는 다음의 매개변수와 반환값을 갖는다.

  • 매개변수: tree(트리)
  • 반환값: 말단 노드의 개수

해당 함수는 다음과 같이 구현될 수 있다. 

def count_leaves(tree):
  return sum(i not in tree.values() for i in tree)

말단 노드는 자식 노드가 존재하지 않는 노드를 일컫는다.


tree 는 {Node: Parent} 의 데이터가 나열된 형태로써 존재하는데,
반복문 for i in tree 의 경우 i 는 Node 집합의 원소들이 반복적으로 할당된다.
또한, tree.values() 는 Parent 의 집합을 의미한다.


이때, 

i not in tree.values()

어떤 Node (i) 가 Parent 의 집합 (tree.values()) 에 없다는 것은, 자신을 부모로 하는 노드가 존재하지 않음을 즉, 해당 Node (i) 가 말단 노드임을 나타낸다.


따라서 파이썬의 제너레이터 문법을 사용하여 

i not in tree.values() for i in tree

으로 나타낸 후 이것의 합을 구하면, 말단 노드의 개수가 된다.

sum(i not in tree.values() for i in tree)

5. 제출 코드

1차

맞았습니다

import copy

n = int(input())
tree = dict(enumerate(map(int, input().split())))
remove = int(input())
node_set = set()

tree.pop(remove)
node_set.add(remove)

while node_set:
  temp = copy.deepcopy(tree)
  parent = node_set.pop()

  for i in tree:
    if tree[i] == parent:
      temp.pop(i)
      node_set.add(i)

    tree = temp

count = 0

for i in tree:
  count += i not in tree.values()

print(count)

최초 제출한 코드이다. 문제는 맞았지만 구현이 만족스럽지 못해 재제출하였다.

2차

맞았습니다

from collections import deque

def remove_node(tree, remove):
  removed_tree = dict(tree)
  removed_tree.pop(remove)
  queue = deque([remove])

  while queue:
    parent = queue.popleft()

    for node in tree:
      if tree[node] == parent:
        removed_tree.pop(node)
        queue.append(node)

  return removed_tree

def count_leaves(tree):
  return sum(i not in tree.values() for i in tree)

input()
tree = dict(enumerate(map(int, input().split())))
remove = int(input())

tree = remove_node(tree, remove)
count = count_leaves(tree)

print(count)

너비 우선 탐색 으로 구현된 코드이다.

3차

맞았습니다

def remove_node(tree, remove):
  removed_tree = dict(tree)
  removed_tree.pop(remove)
  
  for node, parent in removed_tree.items():
    if parent == remove:
      removed_tree = remove_node(removed_tree, node)

  return removed_tree

def count_leaves(tree):
  return sum(i not in tree.values() for i in tree)

input()
tree = dict(enumerate(map(int, input().split())))
remove = int(input())

tree = remove_node(tree, remove)
count = count_leaves(tree)

print(count)

깊이 우선 탐색 으로 구현된 코드이다.

관련 포스팅

  • 추가 예정...
728x90
저작자표시

'Computer Science > Baekjoon' 카테고리의 다른 글

[Baekjoon] 10101번 삼각형 외우기 B4 <Short>  (1) 2024.01.20
[Baekjoon] 1193번 분수찾기 S5 <Short>  (0) 2023.12.22
[Baekjoon] 2839번 설탕 배달 B1 <Short>  (0) 2023.11.12
[Baekjoon] 2292번 벌집 B2 <Short>  (0) 2023.10.22
[Baekjoon] 2096번 내려가기 G5  (0) 2023.09.23

'Computer Science/Baekjoon' Related Articles

티스토리툴바