1 minute read

문제

접근 방법

이 문제를 풀 때, 부모 정보로만 leaf node인지 어떻게 판단할 것인지 그리고 제거하는 노드가 주어졌을 때 그 노드와 연결된 자식 노드들은 어떻게 처리할 것인지를 알아내는 것이 어려웠다.

조금 더 생각해보니 그냥 트리를 순회하면서 노드가 자식이 없다면, 또는 제거될 노드만 자식으로 갖고있다면 그 노드는 leaf node이고, 제거 노드로 순회를 확장하지만 않으면 그 자식 노드들은 따로 처리하지 않아도 된다는 것을 알아냈다.

두 트리 순회 알고리즘 dfs랑 bfs로 풀어보았다.

정답 코드 (dfs)

import sys
from collections import deque

input = sys.stdin.readline
"""
각 노드 부모 정보로 graph를 형성할 수 있다.

dfs를 해서 지우려는 노드에 닿았다면 그 부분은 탐색 안함

dfs를 해서 이동한 노드에서 다른 노드로 이동할 수 없다면 그 노드는 leaf node

"""

n = int(input())

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

remove = int(input())

start = 0
graph = [[] for _ in range(n)]
for i in range(len(parents)):
  if parents[i] >= 0:
    graph[parents[i]].append(i)
  elif parents[i] == -1:
    start = i
    

visited = set()
leafs = 0


def dfs(s,r):
  global leafs
  if r==s:
    return
  visited.add(s)

  leaf = True
  for e in graph[s]:
    if e not in visited and e!=r:
      leaf = False
      dfs(e,r)

  if leaf:
    leafs+=1
  #print(f"leaf: {s}는 {leaf}")


dfs(start, remove)

print(leafs)

정답 코드 (bfs)

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
parents = list(map(int, input().split()))

remove = int(input())

start = 0
graph = [[] for _ in range(n)]
for i in range(len(parents)):
  if parents[i] == -1:
    start = i
  else:
    graph[parents[i]].append(i)

def bfs(start):
  if start == remove:
    return 0
  q = deque([start])
  visited = set()
  visited.add(start)

  leaves = 0
  
  while q:
    s = q.popleft()
    is_leaf = True
    for e in graph[s]:
      if e!=remove and e not in visited:
        is_leaf = False
        visited.add(e)
        q.append(e)

    if is_leaf:
      leaves+=1

    
  return leaves

print(bfs(start))

You May Also Enjoy