❓ Question
📖 Before Start
오늘 처음 학습한 트리 자료구조 탐색에 관한 문제를 풀어보았다.
이번 문제는 트리를 구축하고, 이 중 일부를 제거한 나머지 중에서 단말 노드의 수량을 구해야 했다.
트리의 일부를 어떻게 제거할 지, 그리고 제거한 나머지 중에서 단말 노드를 구하는 방법을 얻었다.
✒️ Design Algorithm
특정 노드 를 제거할 경우, 하위의 자식 노드들을 어떻게 전부 제거할 수 있을까?
크기가 N-1 개의 노드를 입력 받은 정보를 토대로 구축하고, 이를 이차원 배열로 표현한다.
그 후, 제거할 노드를 인계 받고 해당 노드의 하위 노드들도 제거 대상 에 모두 포함시킨다.
이후 트리를 순회하며 제거 대상 이 아닌 노드들 중, 단말 노드를 찾아 총 갯수를 구한다.
BFS 탐색 으로 트리에서 제거 대상인 노드들을 먼저 선별해보자.
- 제거 대상 여부를 판별하는 list인
removed_list를 선언하고, 값을False로 초기화 한다. - 이후, 제거해야 할 노드를 입력 받고,
BFS탐색을 통해 자식 노드까지 제거 대상에 포함시킨다. - 단말 노드를 찾는 과정에서, 해당 노드가 제거 대상 이라면 자동으로 탐색 대상에서 제외시킨다.
- 그런 뒤, 나머지 노드들 중에서 자식 노드의 수량이
0인 노드를 찾아 갯수를 센다.
💻 Making Own Code
❌ Wrong Code
import sys
from collections import deque
read = sys.stdin.readline
N = int(read())
tree = [list() for _ in range(N)]
root = 0
for i, value in enumerate(map(int, read().split())):
if value != -1:
tree[value].append(i)
continue
root = i
def get_removed(removed):
removed_node = []
queue = deque([removed])
while queue:
rm_node = queue.popleft()
# 해당 노드를 제거 대상인 노드로 설정함.
removed_node.append(rm_node)
# 해당 노드가 자식 노드를 가지고 있는지를 판별.
if tree[rm_node]:
# 자식 노드도 제거 대상이므로 덱에 목록을 추가.
for child_node in tree[rm_node]:
queue.append(child_node)
return removed_node
# 제거 대상인 노드를 제외한 나머지 트리 중에서, 단말 노드의 수량을 계산
def bfs(node, removed_list):
leaf_node = 0
visited = [False] * N
queue = deque([node])
while queue:
current_node = queue.popleft()
visited[current_node] = True
# 탐색한 노드가 제거 대상인지를 먼저 판별해야 함.
if current_node in removed_list:
continue
# 만약 해당 노드의 자식 노드가 없다면, 카운트 추가
if not tree[current_node]:
leaf_node += 1
continue
# 자식 노드가 존재한다면, 덱에 목록을 추가해야 함.
for child_node in tree[current_node]:
# 해당 노드를 방문했는지를 파악해야 함.
if not visited[child_node]:
queue.append(child_node)
return leaf_node
removed_list = get_removed(int(read()))
result = bfs(root, removed_list)
print(result)
하지만 원인 모를 반례가 있는지, 자꾸만 80% 언저리에서 오답 처리되었다.
대체 무엇이 문제일까, 여기서부터 1차 멘붕이 시작되었다. 분명 잘 한 것 같다고 생각했는데...
한참을 고민하던 중 , 불현듯 이런 생각이 들었다. 만약, 제거 후 남은 노드가 루트 노드 뿐이라면?
고민은 길지 않았다, 바로 2차 분석 에 들어갔다.
상단의 코드에서는 단순히 탐색 과정에서 해당 노드가 제거 대상 에 포함되는지만 체크하였다.
하지만 그 이후 자식 노드의 수량을 판별하는 과정에서는, 제거 대상 인 노드를 배제하지 않았다.
반례를 찾고 나서는 일사 천리였다. 자식 노드의 수량을 체크하는 구문만 수정하였다.
✅ Correct Code
import sys
from collections import deque
read = sys.stdin.readline
N = int(read())
tree = [list() for _ in range(N)]
root = 0
for i, value in enumerate(map(int, read().split())):
if value != -1:
tree[value].append(i)
else:
root = i
def get_removed(removed):
removed_node = [False] * N
queue = deque([removed])
while queue:
rm_node = queue.popleft()
# 해당 노드를 제거 대상인 노드로 설정함.
removed_node[rm_node] = True
# 해당 노드가 자식 노드를 가지고 있는지를 판별.
if tree[rm_node]:
# 자식 노드도 제거 대상이므로 덱에 목록을 추가.
for child_node in tree[rm_node]:
queue.append(child_node)
return removed_node
# 제거 대상인 노드를 제외한 나머지 트리 중에서, 단말 노드의 수량을 계산
def bfs(node, removed_list):
leaf_node = 0
visited = [False] * N
visited[node] = True
queue = deque([node])
while queue:
current_node = queue.popleft()
# 탐색한 노드가 제거 대상인지를 먼저 판별해야 함.
if removed_list[current_node]:
continue
# 해당 노드의 자식 노드 중에서, 삭제 예정인 노드를 제외함.
child_nodes = [nd for nd in tree[current_node] if not removed_list[nd]]
# 그 후 남은 자식 노드가 0이라면, 단말 노드이므로 카운트 1 추가.
if len(child_nodes) == 0:
leaf_node += 1
continue
# 남은 자식 노드가 존재한다면, 덱에 목록을 추가해야 함.
for child_node in child_nodes:
# 해당 노드를 아직 방문하지 않았다면, 방문 처리를 진행함.
if not visited[child_node]:
visited[child_node] = True
queue.append(child_node)
return leaf_node
removed_list = get_removed(int(read()))
result = bfs(root, removed_list)
print(result)자식 노드의 목록이 담긴 tree[current_node]에서, 제거 대상을 제외한 나머지 노드를 별도로 추출하였다.
이렇게 코드를 수정하니 제거 후 남은 트리 구성 요소가 루트 노드 만 있을 경우 1이 잘 출력되었다.
이전 코드에서는 루트 노드에 자식 노드가 존재한다고 판단했기에, 단말 노드의 수량이 0 이 나왔다.
5
-1 0 1 1 1
1
요 반례를 고려하여 코드를 재작성하니, 그제야 정답 처리 를 해주셨다.
왜 진작 이 반례를 생각하지 못했을까 아직 갈 길이 멀다
이번 문제도 영 호락호락하지가 않다. 트리 자료 구조도 많은 연습이 필요해보인다...
📖 Conclusion
📒 github Code link
백준 은 꾸준히 푸는 것이 중요하다고 생각한다. 요새 React 학습과 공모전을 병행하느라 정신이 없지만!
그래도 조금씩 풀다보면 나의 2차 목표인 골드 I 에 도달할 수 있지 않을까? 기대가 된다!
