240312 - 트리

[robert-min]

문제

1. boj1991 - 트리 순회 링크
2. boj1240 - 노드사이의 거리 링크
3. boj20955 - 민서의 응급 수술 링크
4. boj2250 - 트리의 높이와 너비 링크
5. boj1967 - 트리의 지름 링크

[robert-min]

boj1991 - 트리 순회

"""
Return : 전위순회, 중위순회, 후위순회 결과
- 노드, 왼쪽 자식노드, 오른쪽 자식 노드

- class Node
- 노드 입력
"""
import sys
input = sys.stdin.readline

N = int(input())
inputs = []
for _ in range(N):
    inputs.append(input().split())

class Node:
    def __init__(self, val, left=None, right=None) -> None:
        self.val = val
        self.left = left
        self.right = right

trees = {}
for val, left, right in inputs:
    trees[val] = Node(val, left, right)

def preorder(node: Node):
    print(node.val, end="")
    if node.left != ".":
        preorder(trees[node.left])
    if node.right != ".":
        preorder(trees[node.right])

def midorder(node: Node):
    if node.left != ".":
        midorder(trees[node.left])
    print(node.val, end="")
    if node.right != ".":
        midorder(trees[node.right])

def afterorder(node:Node):
    if node.left != ".":
        afterorder(trees[node.left])
    if node.right != ".":
        afterorder(trees[node.right])
    print(node.val, end="")

preorder(trees['A'])
print()
midorder(trees["A"])
print()
afterorder(trees["A"])

[robert-min]

boj1240 - 노드사이의 거리

"""
Return : 두 노드 사이의 거리 출력

a -> b : dfs로 b를 찾을때까지, distance + w
"""
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))

from collections import deque
def bfs(start, end):
    visited = [-1] * (N+1)
    visited[start] = 0
    Q = deque([(start, 0)])
    while Q:
        now, distance = Q.popleft()
        for nx, w in graph[now]:
            temp = distance + w
            if visited[nx] == -1:
                visited[nx] = temp
                Q.append((nx, temp))
        # end 찾으면 종료
        if visited[end] != -1: break
    return visited

for _ in range(M):
    a, b = map(int, input().split())
    visited = bfs(a, b)
    print(visited[b])

[robert-min]

boj20955 - 민서의 응급 수술

• Union-Find 문제

"""
Return : 하나의 트리 형태로 연결하기 위해 필요한 최소 연산 횟수
- 연결되지 않은 두 뉴런 연결
- 이미 연결된 뉴련 끊기
  - 트리에 순회가 발생하는 경우 

- 모든 뉴런을 연결하기 위해서는 최종적으로 부모 노드가 하나의 노드로 union-find
  - cnt += 1
"""
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
parents = [i for i in range(N+1)]

def find(x):
    if parents[x] != x:
        return find(parents[x])
    return x

def union(a, b):
    a = find(a)
    b = find(b)

    if a == b:
        return

    if rank[a] > rank[b]:
        parents[b] = a
    elif rank[a] < rank[b]:
        parents[a] = b
    else:
        parents[a] = b
        rank[b] += 1

cnt = 0
rank = [0] * (N+1)
for _ in range(M):
    u, v = map(int, input().split())

    if find(u) == find(v):
        cnt += 1
    else:
        union(u, v)

set_count = set()
for i in range(1, N+1):
    set_count.add(find(i))

print(cnt + len(set_count) - 1)