(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 1272 특별 노드 파이썬(Python)
트리에서 DP를 수행하는 문제.
기본적으로, 각 노드가 특별노드가 되거나 안 되거나, 두 가지 경우이므로 최대 \(2^{1000}\)만큼의 시간이 걸린다.
당연히, 이 경우를 모두 볼 필요는 없고, 중복되는 부분문제가 있다는 것에 착안해 DP로 풀면 된다.
임의의 한 노드 입장에서, 다른 조상 노드들이 특별 노드든 아니든, 그 노드의 가중치는 가장 가까운 조상 노드의 영향만 받는다.
그 말은, 일단 어떤 노드가 특별 노드가 되면, 그 뒤의 계산은 단 한 번만 하면 된다는 뜻이다.
왜냐하면, 그 노드를 루트 노드로 하는 부분트리의 가중치는 그 노드 위의 노드들의 영향을 받지 않기 때문이다.
예를 들어, 1번 노드부터 5번 노드까지 순서대로 연결된 Skewed Tree를 생각해보자.
중간에 있는 3번 노드가 특별 노드라면, 2번이 특별 노드든 아니든 3번과 그 밑에 있는 노드들(3, 4, 5)은 모두 가중치가 변하지 않는다.
경우의 수에 따른 탐색 트리를 그려 보면, 완전탐색일 때는 깊이가 \(N\)인 포화 이진 트리가 그려질 것이다.
반면, DP를 사용하여 중복 계산을 제거하면 현재 노드가 특별 노드인 경우는 단 한 번만 분화하고, 나머지 경우는 모두 현재 노드가 특별 노드가 아닐 때만 분화하게 된다. 이 경우 계산 횟수는 대략적으로 \(O(\sum (N - 1) + 1) = O(N^2)\)이 된다.
즉, 제곱 시간 안에 답을 구할 수 있다.
이제 구현하면 된다. 먼저 루트에서부터 트리를 탐색해서 각 노드의 자식 노드를 구한다.
그 이후 DP를 이용해 각 노드를 루트 노드로 하는 부분트리의 가중치를 구하고, 이를 이용해 정답을 구하면 된다.
이때, 고려할 변수는 가장 가까운 특별 노드(prec)와 현재 노드(node)의 두 개이므로 여기서도 \(O(N^2)\)임을 알 수 있다.
#!python
from sys import stdin, setrecursionlimit
from functools import cache
input = stdin.readline
setrecursionlimit(10**6)
INF = float('inf')
# 가장 가까운 특별 노드가 prec일 때, node가 루트인 부분트리의 총 가중치
@cache
def solve(prec, node):
# ans를 현재 노드(node)의 가중치로 초기화
# 만약 현재 노드가 특별 노드이면 w[node], 아니면 w[node] - w[prec]
ans = w[node] if prec == node else w[node] - w[prec]
# 각 자식들에 대해,
# 그 노드가 특별 노드인 경우(succ, succ)와 아닌 경우(prec, succ)으로 나누어 더 작은 쪽을 더한다
for succ in child[node]:
ans += min(solve(succ, succ), solve(prec, succ))
return ans
# 입력 받음
# 노드 번호가 1부터 시작하므로 1씩 빼줘서 0부터로 바꿈
n, r = map(int, input().split())
r -= 1
w = list(map(int, input().split()))
# tree는 인접 리스트, visited는 dfs 위한 방문 여부 리스트, child[i]는 i 노드의 자식들 목록
tree = [[] for _ in range(n)]
visited = [False] * n
child = [[] for _ in range(n)]
for _ in range(n - 1):
a, b = map(int, input().split())
tree[a-1].append(b - 1)
tree[b-1].append(a - 1)
# 루트에서부터 dfs를 수행해서 child 리스트를 채운다
visited[r] = True
q = [r]
while q:
node = q.pop()
for succ in tree[node]:
if visited[succ]:
continue
child[node].append(succ)
visited[succ] = True
q.append(succ)
# 루트 노드가 특별 노드일 때(prec = r), 루트 노드를 루트로 하는 그래프(node = r)의 총 가중치
print(solve(r, r))
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...