[알고리즘] Tree (python)

트리는 계층형 트리 구조를 시뮬레이션하는 추상 자료형으로 서브트리로 구성되어 있다.
트리의 자식도 트리, 자식의 자식도 트리라는 의미이다.
이때문에 트리는 재귀로 정의된 자기참조 자료구조 속성을 가진다.
짧게 말해 순환 구조를 가지지 않으므로
순환구조를 갖지 않는 그래프이다.

백준 1967 트리의 지름
시작과 끝이 어디인지 상관없이 최대 길이를 구하는 문제이다
당연히 leaf 에서 leaf가 최대 길이일것이다

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

tree = defaultdict(list)
#부모, 자식, 간선길이
n = int(input())
for _ in range(n-1):
    p, c, d = map(int, input().split())
    tree[p].append((c,d))
    tree[c].append((p,d))


visited = [-1]*(n+1)
def dfs(curr, curr_dist):
    for next, add_dist in tree[curr]:
        if visited[next] == -1:
            visited[next] = curr_dist+add_dist
            dfs(next, curr_dist+add_dist)

visited[1] = 0
dfs(1,0)
new_start = visited.index(max(visited))
visited = [-1]*(n+1)
visited[new_start] = 0
dfs(new_start, 0)
print(max(visited))

루트에서 시작해 가장 먼 leaf를 찾고, 그 leaf에서 다시 탐색을 시작해 leaf-leaf 최대 길이를 구했다

백준 1068 트리
트리가 주어지고 삭제할 노드가 주어진다
삭제한 노드의 자식들도 모두 삭제된다.
입력으로 자신의 부모를 알려주고, 부모가 -1이라고 주어진 노드가 root node이다.

삭제한 노드를 제외하고 리프 노드의 개수를 출력하면 된다.

import sys
input = sys.stdin.readline
from collections import defaultdict, deque

def bfs(c):
    leaf = 0
    q = deque()
    q.append(c)
    while q:
        curr = q.popleft()
        flag = False
        for next in tree[curr]:
            q.append(next)
            flag = True
        if not flag:
            leaf += 1
    return leaf


n = int(input())
l = list(map(int, input().split()))
delete = int(input())

if delete == l.index(-1) :
    print(0)
else:
    tree = defaultdict(list)
    for child, parent in enumerate(l):
        if parent != -1 and child != delete:
            tree[parent].append(child)
    print(bfs(l.index(-1)))
    

bfs는 특별한 기능 없이 leaf노드의 개수를 세어 주도록 했다.
문제 조건은 간단하게 삭제한 노드만 트리에 포함시키지 않는 방법을 택했다.
그 노드만 포함시키지 않아도 그 자식노드가 tree에는 존재하지만 bfs를 진행하며 queue에 포함되지 않기 때문에 문제가 없다.

root node를 삭제시킬 경우만 예외를 작성해서 처리했다.
처음에는 무조건 인덱스0로 주어진 node가 root node라고 생각해서 시간이 조금 걸렸다.

백준 11438 LCA 2