Tree & Binary Search Tree

트리(Tree)란?

값을 가진 노드(node)와 노드들을 연결하는 간선(edge)로 이루어진 자료구조
최 상단에 있는 노드를 root노드라고 하며 자식 노드, 부모 노드의 관계가 있다.

몇가지 특징

• 트리에는 사이클이 존재할 수 없다. (만약 사이클이 만들어진다면, 그것은 트리가 아니고 그래프다)
• 모든 노드는 자료형으로 표현이 가능하다.
• 루트에서 한 노드로 가는 경로는 유일한 경로 뿐이다.
• 노드의 개수가 N개면, 간선은 N-1개를 가진다.

트리의 순회 방식

전위 순회(pre-order)
각 루트(Root)를 순차적으로 먼저 방문하는 방식이다.
(Root → 왼쪽 자식 → 오른쪽 자식)
-> 1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14

중위 순회(in-order)
왼쪽 하위 트리를 방문 후 루트(Root)를 방문하는 방식이다.
(왼쪽 자식 → Root → 오른쪽 자식)
-> 8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7

후위 순회(post-order)
왼쪽 하위 트리부터 하위를 모두 방문 후 루트(Root)를 방문하는 방식이다.
(왼쪽 자식 → 오른쪽 자식 → Root)
-> 8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1

레벨 순회(level-order)
루트(Root)부터 계층 별로 방문하는 방식이다.
-> 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14

문제 - 트리의 지름

위 문제는 가중치가 있는 트리의 가장 넓은 지름을 구하는 문제다.
먼저 트리를 그래프로 만들어주고 dfs로 시작노드에서부터 각 노드까지의 거리를 탐색하여 저장하려고 한다.
이때 시작 노드를 무엇으로 잡아야 최대 지름을 구할 수 있을까?
처음에는 늘 그랬듯 1번 노드를 시작으로 잡았다.
그렇게 되면 가장 높은 높이는 구할 수 있지만 가장 넓은 지름이라고는 단정지을 수 없다.
그래서 1번 노드와 가장 먼 노드를 기준으로 다시 한번 구해주었다. 즉 아래 두 과정을 거치는 것이다.

1. 트리에서 아무 노드나 잡고 그 노드에 대한 가장 먼 노드를 구하고 이 노드를 n1이라고 하자.
2. n1 에대한 가장 먼 노드를 한번 더 구한다. 이 노드를 n2라고 하자. 이제 n1과 n2의 거리가 트리의 지름이 된다.

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs(node, distance):
    global graph, visited
    for child, w in graph[node]:
        if visited[child] == -1:
            visited[child] = distance + w
            dfs(child, distance + w)
            
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    parent, child, w = map(int, input().split(' '))
    graph[parent].append([child, w])
    graph[child].append([parent, w])

visited = [-1 for _ in range(n+1)]
visited[1] = 0
dfs(1, 0)

start = visited.index(max(visited))
visited = [-1 for _ in range(n+1)]
visited[start] = 0
dfs(start, 0)
print(max(visited))