백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-1068 트리 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/1068

반응형

---

솔루션 살펴보기!!

# Authored by : ap4o
# Co-authored by : -
# Link : http://boj.kr/7c236d89d3c64e59920ab0851d08f40d

import sys
sys.setrecursionlimit(10000)

# Initialize the tree with 51 possible nodes (0 to 50)
tree = [[] for _ in range(51)]
answer = 0

def dfs(idx):
    global answer
    is_leaf = True
    for child in tree[idx]:
        is_leaf = False
        dfs(child)
    if is_leaf:
        answer += 1

def main():
    global tree, answer
    input = sys.stdin.read().split()
    it = iter(input)
    
    # Read number of nodes
    N = int(next(it))
    
    parent = []
    root = -1
    for i in range(N):
        tmp = int(next(it))
        parent.append(tmp)
        if tmp == -1:
            root = i
        else:
            tree[tmp].append(i)
    
    # Read the node to delete
    del_node = int(next(it))
    
    # Delete the node by clearing its children
    tree[del_node].clear()
    
    # Remove the deleted node from its parent's children list
    for i in range(N):
        if del_node in tree[i]:
            tree[i] = [child for child in tree[i] if child != del_node]
    
    # If the deleted node is not the root, perform DFS
    if del_node != root:
        dfs(root)
    else:
        # If the root is deleted, there are no leaf nodes
        answer = 0
    
    # Print the number of leaf nodes
    print(answer)

if __name__ == "__main__":
    main()

---

코드 흐름과 풀이 전략

이 코드는 트리 구조에서 특정 노드를 삭제한 후 남은 트리에서 **리프 노드(leaf node)**의 개수를 계산하는 문제를 해결합니다. 아래는 코드의 주요 흐름과 풀이 전략을 설명한 내용입니다.

1. 입력 처리

• N: 트리의 노드 개수를 입력받습니다.
• parent: 각 노드의 부모 정보를 담습니다. -1이면 해당 노드가 루트임을 의미합니다.
• tree: 각 노드에 대해 자식 노드 목록을 관리하는 리스트로, 51개의 빈 리스트로 초기화됩니다. 각 노드는 0번에서 50번까지 사용할 수 있도록 설정되어 있습니다.
• root: 트리의 루트 노드를 추적합니다. 부모 정보가 -1인 경우 그 노드가 루트입니다.
• del_node: 삭제할 노드를 입력받습니다.

2. 트리 구성

• 주어진 부모 정보를 바탕으로 tree 리스트에 각 노드의 자식을 추가합니다. 부모-자식 관계를 트리 구조로 표현합니다.
• 루트 노드도 추적하여 이후 DFS를 시작할 노드를 결정합니다.

3. 노드 삭제

• del_node(삭제할 노드)에 대해 자식 노드를 모두 삭제(clear())하여 삭제된 노드가 자식 노드를 가질 수 없도록 합니다.
• 삭제된 노드를 부모의 자식 리스트에서도 제거합니다. 이를 위해 리스트 내포를 사용하여 해당 노드를 리스트에서 제거합니다.

4. DFS(깊이 우선 탐색)로 리프 노드 계산

• dfs(idx) 함수는 재귀적으로 노드를 탐색하며, 자식이 없는 노드를 리프 노드로 간주하여 answer에 1을 더합니다.
• 각 노드에 대해 자식이 있으면 자식으로 계속해서 재귀적으로 내려가며 탐색하고, 자식이 없으면 리프 노드로 판단합니다.
• 삭제된 노드가 루트가 아닌 경우에만 루트에서 DFS를 시작합니다. 루트가 삭제되었다면 리프 노드가 존재하지 않으므로 탐색을 하지 않고 결과를 0으로 설정합니다.

5. 결과 출력

• DFS를 통해 계산된 리프 노드의 개수를 출력합니다.

풀이 전략 요약

1. 트리를 부모-자식 관계로 구성합니다.
2. 삭제할 노드를 삭제하고, 부모 노드와의 연결을 제거합니다.
3. 루트 노드에서부터 DFS를 사용하여 리프 노드(자식이 없는 노드)를 탐색하고 개수를 셉니다.
4. 루트가 삭제된 경우에는 리프 노드가 없으므로 바로 0을 출력합니다.

---

728x90

코딩 면접에서 알아야 할 주요 개념

1. 트리 구조 (Tree Structure):
   • 트리는 계층적 구조를 가지는 비순환 연결 그래프입니다. 트리의 각 노드는 부모-자식 관계로 이루어져 있으며, 이 문제에서는 부모 리스트를 기반으로 트리를 구성합니다.
   • 트리에서 루트 노드, 자식 노드, 리프 노드와 같은 개념을 명확히 이해해야 합니다.
2. DFS (Depth-First Search, 깊이 우선 탐색):
   • DFS는 트리나 그래프에서 자식 노드 또는 인접한 노드를 깊게 탐색한 후, 그 후에 다른 노드를 탐색하는 방법입니다.
   • 이 문제에서는 DFS를 사용하여 리프 노드를 찾고 계산하는 데 활용됩니다. DFS는 트리 구조에서 매우 자주 쓰이는 탐색 기법입니다.
3. 리프 노드 (Leaf Node):
   • 리프 노드는 자식이 없는 노드를 의미합니다. 이 문제의 목표는 삭제 후 남은 트리에서 리프 노드를 세는 것입니다.
   • DFS로 트리를 순회할 때 자식이 없으면 그 노드를 리프 노드로 처리합니다.
4. 재귀 (Recursion):
   • DFS는 재귀적으로 호출되며, 트리의 각 노드를 탐색합니다. 재귀는 함수가 자기 자신을 호출하는 개념으로, 트리나 그래프에서 탐색할 때 자주 사용됩니다.
5. 노드 삭제 및 트리 업데이트:
   • 트리 구조에서 특정 노드를 삭제하면 그와 연결된 자식 노드나 부모 노드와의 관계를 끊어야 합니다. 이를 명확히 처리해야 트리가 제대로 유지됩니다.
   • 이 코드에서는 부모 노드에서 자식 리스트를 업데이트하고, 삭제된 노드의 자식 리스트도 비워 처리합니다.