<백준(파이썬)> 1068번: 트리

 

🤖

 

문제

https://www.acmicpc.net/problem/1068

1068번: 트리

 

풀이

삭제할 노드를 부모로 가지는 노드를 모두 삭제하고, 이어서 삭제된 노드들을 부모로 가지는 노드들을 삭제하는 과정을 반복하는 방식으로 풀어나갔습니다.

이러한 문제의 접근 방법은 깊이우선탐색(DFS)으로 볼 수 있을 것입니다.

하지만 결과로 '틀렸습니다'가 계속 나오는 바람에 꽤나 헤맸습니다.

조건식을 잘못 작성한 것이 원인이었습니다.

루트만 남는 경우 루트를 리프 노드로 카운트 해야 하는데, 루트 노드를 무조건 카운트에서 제외하는 실수를 했습니다.

전체 코드는 아래와 같습니다.

N = int(input())
parent_of_ = list(map(int, input().split()))
NODE_TO_DELETE = int(input())

delete_list = list()
delete_list.append(NODE_TO_DELETE)
# 삭제할 노드의 부모노드 연결 끊기 (의미없는 99 할당)
parent_of_[NODE_TO_DELETE] = 99

while delete_list:
    delete = delete_list.pop()
    for node in range(len(parent_of_)):
        if parent_of_[node] == delete:
            delete_list.append(node)
            parent_of_[node] = 99

leaf_count = 0

for node in range(len(parent_of_)):
    if parent_of_[node] == 99:
        continue
    if node not in parent_of_:
        leaf_count += 1

print(leaf_count)

전체 코드를 몇가지 뭉치로 나누어 보겠습니다..

1. 문제에서 주어진 입력값을 받습니다.

# 노드의 개수
N = int(input())
# 인덱스: 요소 => 노드: 부모 노드
parent_of_ = list(map(int, input().split()))
# 삭제할 노드
NODE_TO_DELETE = int(input())

2. 삭제할 노드를 리스트 자료형에 따로 저장해두고, 삭제된 노드의 부모에는 99라는 의미없는 숫자를 부여합니다.

# 삭제할 노드를 삭제 리스트에 저장
delete_list = list()
delete_list.append(NODE_TO_DELETE)
# 삭제할 노드의 부모노드 연결 끊기 (의미없는 99 할당)
parent_of_[NODE_TO_DELETE] = 99

3. 삭제 리스트에 노드가 있으면, 하나씩 pop하여 그 노드를 부모로 가지는 노드가 있는지 확인합니다.

위 조건을 만족하는 노드가 있으면 삭제 리스트에 추가하고, 삭제의 의미로 99를 할당합니다.

# 리스트에 삭제할 노드가 남아 있으면?
while delete_list:
    # 삭제할 노드를 리스트에서 하나 빼냄
    delete = delete_list.pop()
    # 전체 노드를 하나씩 돌면서
    for node in range(len(parent_of_)):
        # 노드의 부모노드가 삭제할 노드인 경우
        if parent_of_[node] == delete:
            # 해당 노드도 삭제 리스트에 저장
            delete_list.append(node)
            # 삭제할 노드의 부모노드 연결 끊기
            parent_of_[node] = 99

4. 노드 리스트의 노드를 하나씩 돌면서 조건식을 확인합니다.

부모가 99인 노드를 제외하고, 어느 노드의 부모도 아닌 노드는 리프노드이므로 카운트를 1씩 증가시킵니다.

# 리프노드 카운트 0으로 초기화
leaf_count = 0
# 전체 노드를 하나씩 돌면서
for node in range(len(parent_of_)):
    # 노드의 부모가 99이면 삭제된 노드라서 continue
    if parent_of_[node] == 99:
        continue
    # 노드가 다른 어떤 노드의 부모도 아닌 경우 leaf_count + 1
    if node not in parent_of_:
        leaf_count += 1

# 리프노드의 개수
print(leaf_count)

 

(틀렸던 조건식) 부모가 -1인 루트 노드를 무조건 제외하는 코드를 작성했습니다. 루트만 남게 되는 경우, 리프 노드가 되므로 아래에서 parent_of_[node] == -1 이라는 조건을 삭제하였습니다.

if parent_of_[node] == -1 or parent_of_[node] == 99:
    continue