[자료구조 및 알고리즘] Tree에 관한 모든 것

문제 풀다가 알게된 새로운 지식이라 정리하게 됐습니다. (본인 공부 및 기록용)😁

Tree란?

Tree는 그래프의 한 종류로, 사이클이 없는 연결 그래프를 의미합니다.(양방향, 여러 개의 노드가 서로 하나의 경로로 연결된 계층 구조를 가진 데이터 구조)

Tree 구성요소

• 루트 노드(Root Node): Tree의 최상단에 위치한 노드입니다. 부모 노드가 없는 노드입니다.
• 부모 노드(Parent Node): 특정 노드와 직접 연결된 상위 노드입니다.
• 자식 노드(Child Node): 특정 노드와 직접 연결된 하위 노드입니다.
• 리프 노드(Leaf Node): 자식 노드가 없는 노드입니다.
• 서브트리(Subtree): 특정 노드를 루트로 하는 하위 트리입니다.
• 높이(Height): 루트 노드에서 가장 먼 리프 노드까지의 거리입니다.
• 깊이(Depth): 루트 노드에서 특정 노드까지의 거리입니다.

Tree 종류

• 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.
• 완전 이진 트리(Complete Binary Tree): 모든 레벨이 꽉 차 있거나, 마지막 레벨만 노드가 채워져 있는 이진트리입니다.
• 포화 이진 트리(Full Binary Tree): 모든 노드가 두 개의 자식 노드를 가지는 이진 트리입니다.
• 균형 이진 트리(Balanced Binary Tree): 모든 리프 노드의 높이가 같거나, 하나 차이가 나는 이진 트리입니다.
• AVL 트리(AVL Tree): 모든 노드의 두 자식 트리의 높이 차이가 1 이하인 이진 탐색 트리입니다.
• 레드-블랙 트리(Red-Black Tree): 특정 규칙을 따르며 노드를 색으로 구분하여 균형을 유지하는 이진 탐색 트리입니다.

Tree DP

Tree DP(Tree Dynamic Programming)은 트리 구조에서 동적 계획법(DP)을 적용하는 기법입니다. 주로 트리의 루트부터 리프 노드까지의 경로를 따라가며 문제를 해결합니다. Tree DP는 트리의 특성을 활용하여 중복 계산을 피하고, 효율적으로 문제를 해결하는 데 사용됩니다.

Tree DP 주요 개념

• DFS(Depth-First Search): 트리를 순회하면서 각 노드의 정보를 계산하는데 사용됩니다. 흔히들 생각하는 DFS, BFS에서 DFS와 같은 개념입니다.
• 메모이제이션(Memoization): 이미 계산된 값을 저장하여 중복 계산을 피하는 기법입니다.
• 트리 분할(Tree Partition): 트리를 부분 문제로 나누어 해결하는 방법

예제

1. 트리의 지름

트리의 특성을 이용한 문제

1) 임의의 하나의 노드에서 가장 먼 노드(A)를 찾는다. 2) A 노드에서 가장 먼 노드(B)를 찾는다 3) A와 B간의 거리가 트리의 지름이다.

def tree_diameter(tree):
    def bfs(start):
        visited = [-1] * len(tree)
        queue = deque([start])
        visited[start] = 0
        farthest_node = start
        
        while queue:
            node = queue.popleft()
            for neighbor in tree[node]:
                if visited[neighbor] == -1:
                    visited[neighbor] = visited[node] + 1
                    queue.append(neighbor)
                    farthest_node = neighbor
        
        return farthest_node, visited[farthest_node]
    
    # Step 1: 임의의 노드 (0번 노드)에서 가장 먼 노드 A를 찾기
    node_A, _ = bfs(0)
    
    # Step 2: 노드 A에서 가장 먼 노드 B를 찾기
    node_B, diameter = bfs(node_A)
    
    return diameter

2-1. Tree DP

프로그래머스 등대

2-2. Tree DP

트리가 주어졌을 때, 트리의 각 노드는 마을을 나타내며, 각 마을에는 특정 수의 주민이 살고 있습니다. 일부 마을을 선택하여 우수 마을로 지정하려고 합니다. 우수 마을로 지정된 마을이 인접한 마을은 우수 마을로 지정될 수 없습니다. 우수 마을로 지정된 마을의 주민 수의 합을 최대화하는 프로그램을 작성하세요.

첫 줄에 마을의 수 N이 주어집니다. (1 ≤ N ≤ 10,000)
두 번째 줄에는 각 마을의 주민 수가 주어집니다.
다음 N-1 줄에는 두 마을을 잇는 도로가 주어집니다. 도로는 트리를 형성합니다.

우수 마을로 지정된 마을의 주민 수의 합의 최댓값을 출력합니다.

example: 
6
10 1 5 10 10 1
1 2
1 3
2 4
3 5
3 6

print:
31

def dfs(node):
    visited[node] = True
    dp[node][0] = 0 # node를 우수마을로 선정하지 않은 경우
    dp[node][1] = populations[node] # node를 우수마을로 선정한 경우

    for neighbor in tree[node]:
        if not visited[neighbor]:
            dfs(neighbor)
            dp[node][0] += max(dp[neighbor][0], dp[neighbor][1]) # 주변이 우수 마을로 선정되든 안되든 상관없음
            dp[node][1] += dp[neighbor][0] # 주변 마을이 우수마을이 된 경우에는 옆에가 우수말로 선정되지 않았어야함

n = int(input().strip())
populations = [0] + list(map(int, input().strip().split()))
tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().strip().split())
    tree[u].append(v)
    tree[v].append(u)

dp = [[0] * 2 for _ in range(n + 1)]
visited = [False] * (n + 1)

dfs(1)
print(max(dp[1][0], dp[1][1]))