이번에는 트리와 관련된 문제들을 동적계획법을 적용하여 해결하는 문제들을 알아본다.
1. 트리와 쿼리 (https://www.acmicpc.net/problem/15681)
트리의 노드가 N개이며 루트가 R번일 때, 주어진 N-1 개의 간선으로 트리를 구성하고 이어서 주어지는 Q 개의 임의의 노드에 대해 각 노드를 루트로 하는 서브트리에 속한 노드의 갯수를 구하는 문제이다.
트리를 구성하는 방법은 인접리스트로 양방향 그래프를 구성하는 것과 같다. 그래프와 달리 인접 노드중 부모노드만 방문 대상에서 제외하면 이미 방문한 노드를 다시 방문할 일은 없기 때문에 별도의 방문처리는 필요하지 않다. 트리를 탐색할 dfs(<노드번호>) 함수가 그 결과로 인자로 받은 노드를 루트로 하는 서브트리의 크기(포함하는 노드의 갯수)를 반환하도록 하면 쿼리로 주어진 각 노드번호 q 에 대해 dfs(q) 가 해답이 된다. 물론 쿼리마다 탐색을 진행하면 비효율적이기 때문에 동적계획법을 적용하여 이미 구한 서브트리의 크기는 메모리에 저장해두고 재사용한다. 이를 구현한 코드는 다음과 같다.
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
def sol15681():
n, r, q = map(int, input().split())
# 트리 구성
g = [[] for _ in range(n+1)]
for _ in range(n-1):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
# 서브트리의 크기
sub = [0] * (n+1)
# 탐색 함수
def dfs(node):
# 자기 자신을 포함하기 때문에 시작 크기는 1
sub[node] = 1
# 자식 노드를 루트로 하는 서브트리의 크기를 모두 더한다
for c in g[node]:
if not sub[c]:
sub[node] += dfs(c)
# 자신이 루트 노드인 서브트리의 크기 반환
return sub[node]
# 루트 노드로부터 탐색 시작
dfs(r)
# 각 쿼리에 대한 해답을 반환
return '\n'.join([str(sub[int(input())]) for _ in range(q)])쿼리가 들어올 때 마다 dfs를 실행할 수도 있지만 편의상 루트 노드에 대해 dfs를 호출하는것으로 전처리를 마친 뒤 답을 반환하였다.
2. 트리의 독립집합(https://www.acmicpc.net/problem/2213)
노드가 N개인 트리와 각 노드의 가중치가 주어졌을 때, 트리의 최대 독립 집합의 크기와 최대 독립 집합을 구하는 문제.
그래프의 독립 집합이란 그래프의 정점의 부분집합 중 집합 안의 모든 정점이 서로 직접 인접해있지 않은 것을 의미한다.
최대 독립 집합을 구하는 문제는 그래프에서는 효율적인 알고리즘을 찾지 못한 NP-하드 문제이지만 트리의 경우 서브트리로 문제를 분할하여 효율적으로 해결할 수 있다. 이 문제를 해결한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2213():
# 노드의 갯수
n = int(input())
# 노드의 가중치
w = [0] + list(map(int, input().split()))
# 트리 구성
g = [[] for _ in range(n + 1)]
for i in sys.stdin:
u, v = map(int, i.split())
g[u].append(v)
g[v].append(u)
# 각 노드를 루트로 하는 서브트리의 경우별 최대 독립 집합 크기
# mis[<노드번호>][0] 은 해당 노드가 포함되지 않았을 경우를,
# mis[<노드번호>][1] 은 해당 노드가 포함된 경우의 최대 독립집합의 크기를 의미한다
mis = [[-1, -1] for _ in range(n + 1)]
# mis의 값을 채우기 위한 탐색 함수
def make_set(prev, cur):
# 현재 노드가 독립집합에 포함되지 않은 경우와 포함된 경우의 최대 독립 집합 크기를 초기화
mis[cur] = [0, w[cur]]
# 현재 노드의 자식 노드 순회하며 최대 독립집합의 크기를 합산
for nxt in g[cur]:
if nxt != prev:
# 자식노드를 포함하지 않는 경우와 포함하는 경우의 최대 독립 집합 크기
inc, ninc = make_set(cur, nxt)
# 현재 노드가 포함된 상태일 경우 자식노드는 포함되지 않은 경우만 고를 수 있다.
mis[cur][1] += inc
# 현재 노드가 포함되지 않은 상태일 경우 자식노드는 모든 경우중 더 큰 값을 고를 수 있다.
mis[cur][0] += max(inc, ninc)
# 현재 노드에서의 최대 독립 집합의 크기를 반환
return mis[cur]
# 실제 최대 독립 집합을 구하기 위한 추적 함수
def trace_set(prev, cur, include):
# 반환할 실제 최대 독립 집합
res = set()
# 현재 노드가 독립 집합에 포함될 수 있으며
# 현재 노드가 포함되는 경우가 포함되지 않는 경우보다 독립 집합의 크기가 커진다면
# 최대 독립 집합에 현재 노드를 최대 독립 집합에 포함
# 현재 노드가 독립집합에 포함되었기 때문에 자식노드들은 포함될 수 없음
if include and mis[cur][1] > mis[cur][0]:
res.add(cur)
include = 0
# 현재 노드가 최대 독립 집합에 포함되지 않는 경우
# 다음 노드가 독립집합에 포함될 가능성이 있음
else:
include = 1
# 현재 노드의 자식노드를 순회
# 각 자식노드를 루트로 하는 서브트리의 최대독립집합을 반환할 최대 독립집합에 합한다.
for nxt in g[cur]:
if nxt != prev:
res |= trace_set(cur, nxt, include)
# 최대 독립 집합 반환
return res
# 탐색 시작
make_set(0, 1)
# 루트 노드로 삼을 1번 노드가 포함된 경우와 포함되지 않은 경우중 큰 쪽을 선택
# 최대 독립 집합의 크기와 최대 독립집합을 오름차순 정렬한 결과를 반환
if mis[1][0] > mis[1][1]:
return str(mis[1][0]) + '\n' + ' '.join(map(str, sorted(trace_set(0, 1, 0))))
else:
return str(mis[1][1]) + '\n' + ' '.join(map(str, sorted(trace_set(0, 1, 1))))문제 해결의 요점은 트리를 탐색하는 dfs 함수가 현재 노드를 루트로 하는 서브 트리에서 현재 노드의 포함 여부에 따른 최대 독립집합의 크기를 반환하도록 하는 것이다. 즉, dfs(p, c) 는 부모 노드가 p인 현재 노드 c 에 대해 c를 루트 노드로 하는 서브트리에서 c가 최대 독립 집합에 포함되지 않는 경우가 포함되는 경우의 최대 독립 집합의 크기를 반환해야한다.
하지만 여기까지만으로는 최대 독립 집합의 크기밖에는 알 수가 없다. 실제로 최대 독립 집합을 구하려면 추적 함수가 필요하다. 특정 노드 k가 최대 독립집합에 포함되기 위한 조건은 다음과 같다.
① k의 부모 노드는 최대 독립 집합에 포함되지 않는다.
② k가 포함되는 경우의 최대 독립 집합의 크기가 포함되지 않는 경우의 최대 독립 집합의 크기보다 크다.
이 조건에 따라 다시한번 트리를 탐색하며 실제로 최대 독립 집합을 구할 수 있다.
3. 우수 마을 (https://www.acmicpc.net/problem/1949)
말은 조금 바뀌었지만 사실상 최대 독립 집합 문제이다. 다만 실제로 독립집합을 구하는 것이 아니라 가중치의 최대합만을 구하는 문제이기에 추적함수는 구현할 필요가 없다. 이를 구현한 코드는 다음과 같다.
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
def sol1949():
# 노드의 갯수
n = int(input())
# 각 노드의 가중치
w = [0]+list(map(int, input().split()))
# 트리 구성
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
# 탐색함수
def dfs(pre, cur):
# 현재 노드가 우수마을에 포함될지 여부에 따른 우수마을 주민 수 합의 최댓값
res = [0, w[cur]]
# 현재 노드의 자식노드들에 대해
for nxt in g[cur]:
if nxt != pre:
inc, ninc = dfs(cur, nxt)
# 현재 노드가 우수마을이 아니라면 다음 노드는 우수마을이거나 우수마을이 아닐 수 있다.
res[0] += max(inc, ninc)
# 현재 노드가 우수마을이라면 다음 노드는 우수마을이 아니어야 한다.
res[1] += inc
return res
# 우수 마을 주민 수 합의 최댓값 반환
return max(dfs(0, 1))추가) 이 문제의 경우 독립집합에 포함되지 않는 노드는 반드시 인접한 노드중에 독립집합에 포함된 노드가 있어야한다는 조건을 추가로 제시하는데, 이는 사실 의미없는 함정 조건이다. 독립집합에 포함되지 않으면서 인접한 노드중 독립집합에 포함되는 노드가 하나도 없는경우가 있다면 본인이 독립집합에 추가될 수 있는데도 추가되지 않은 경우이다. 즉, 이 경우 최대 독립집합이 될 수 없기때문에 평범하게 최대 독립집합을 구하면 자연스레 만족되는 조건이다. 이와같이 굳이 필요없는 조건인데도 혼동을 주기위해 넣는 경우도 있으니 주의가 필요하다.
4. 사회망 서비스(SNS) (https://www.acmicpc.net/problem/2533)
어떤 노드의 인접 노드가 모두 얼리어답터라면 그 노드가 얼리어답터가 아니어도 얼리어답터가 된다. 노드의 갯수가 N인 트리가 주어졌을 때, 트리의 모든 노드가 얼리어답터가 되도록 하기 위해서 최소 몇 개의 노드를 얼리어답터로 만들어야 하는지 구해야한다.
모든 노드를 얼리어답터로 만들기 위해서는 루트 노드가 얼리어답터가 아니라면 그 자식노드는 모두 얼리어답터여야 한다. 루트 노드가 얼리어답터라면 자식노드는 얼리어답터일 수도, 아닐 수도 있다.(둘 중 최적의 값을 고를 수 있다) 이는 최대 독립 집합 문제와는 정반대의 조건이라고 할 수 있다. 즉, 이 문제는 최대 독립 집합을 구했을 때, 최대 독립집합에 포함되지 않은 노드의 갯수를 구하는 문제가 된다. 이를 구현한 코드는 다음과 같다.
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
def sol2533():
# 노드의 갯수
n = int(input())
# 트리 구성
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
# 탐색 함수
def dfs(pre, cur):
# 현재 노드가 최대 독립 집합에 포함되지 않을 때, 포함 될 때의 최대 독립 집합의 크기
res = [0, 1]
# 현재 노드의 자식 노드에 대해
for nxt in g[cur]:
if nxt != pre:
inc, ninc = dfs(cur, nxt)
# 현재 노드가 최대 독립 집합에 포함되지 않는다면
# 자식 노드는 최대 독립 집합에 포함될 수도, 포함되지 않을 수도 있다.
res[0] += max(inc, ninc)
# 현재 노드가 최대 독립 집합에 포함된다면
# 자식 노드는 최대 독립 집합에 포함될 수 없다.
res[1] += inc
return res
# 전체 노드 수에서 최대 독립 집합의 크기를 뺀 값 반환
return n - max(dfs(0, 1))풀이 1 - 최대 독립 집합의 크기를 구하는 코드의 반환 값을 전체 노드 수에서 최대 독립 집합의 크기를 뺀 값으로 변경
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
def sol2533():
# 노드의 갯수
n = int(input())
# 트리 구성
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
# 탐색 함수
def dfs(pre, cur):
# 현재 노드가 얼리어답터가 아닐 때, 얼리어답터일 때의 최소 얼리어답터 수
res = [0, 1]
# 현재 노드의 자식 노드에 대해
for nxt in g[cur]:
if nxt != pre:
inc, ninc = dfs(cur, nxt)
# 현재 노드가 얼리어답터가 아니라면 자식노드는 반드시 얼리어답터여야 한다
res[0] += ninc
# 현재 노드가 얼리어답터라면 자식노드는 얼리어답터일 수도, 아닐 수도 있다.
res[1] += min(inc, ninc)
return res
# 최소 얼리어답터 수 반환
return min(dfs(0, 1))풀이 2 - 최대 독립 집합을 구하는 코드에서 dfs 내의 동작을 역으로 변경
'코딩테스트 > 알고리즘' 카테고리의 다른 글
| #22 기하 - CCW(Counter-ClockWise) 2 (0) | 2021.08.27 |
|---|---|
| #21 기하 - CCW(Counter-ClockWise) 1 (0) | 2021.08.25 |
| #19 완전 탐색 - BFS(Breadth First Search) (0) | 2021.08.21 |
| #18 완전 탐색 - DFS(Depth First Search) (0) | 2021.08.20 |
| #17 동적 계획법(Dynamic Programming) 1 - 기본 (0) | 2021.08.19 |