Toolofv 님의 블로그

[Python] 백준 - 2213 트리의 독립집합 본문

Algorithm

[Python] 백준 - 2213 트리의 독립집합

Toolofv 2024. 7. 15. 23:22
반응형

문제

그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 간선이 없으면) S를 독립 집합(independent set)이라고 한다. 독립 집합의 크기는 정점에 가중치가 주어져 있지 않을 경우는 독립 집합에 속한 정점의 수를 말하고, 정점에 가중치가 주어져 있으면 독립 집합에 속한 정점의 가중치의 합으로 정의한다. 독립 집합이 공집합일 때 그 크기는 0이라고 하자. 크기가 최대인 독립 집합을 최대 독립 집합이라고 한다.

문제는 일반적인 그래프가 아니라 트리(연결되어 있고 사이클이 없는 그래프)와 각 정점의 가중치가 양의 정수로 주어져 있을 때, 최대 독립 집합을 구하는 것이다.

 

입력

첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 가중치이다(1 ≤ i ≤ n). 셋째 줄부터 마지막 줄까지는 간선의 리스트가 주어지는데, 한 줄에 하나의 간선을 나타낸다. 간선은 정점의 쌍으로 주어진다. 입력되는 정수들 사이에는 빈 칸이 하나 있다. 가중치들의 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 최대 독립집합의 크기를 출력한다. 둘째 줄에는 최대 독립집합에 속하는 정점을 오름차순으로 출력한다. 최대 독립 집합이 하나 이상일 경우에는 하나만 출력하면 된다.

 

 

문제해결방법 - (구글링 참조)

 

1. 독립집합이란 개념이 처음에는 이해가 되지 않았는데, 트리 구조에서 간선으로 연결되지 않은 노드 조합이라고 생각하면 되는 듯하다. 아래 그림처럼 노드 (1, 3, 5, 7) 같은 경우이다. (1, 3, 5, 6), (2, 4, 6)도 독립집합이다.

 

<트리의 독립집합 중 최대독립집합>

 

 

2. DFS 알고리즘은 깊이우선탐색으로 재귀함수로 가장 깊은 곳에서부터 리턴을 하게 된다. 위 예제라면 리턴 순서는 (5 -> 4 -> 3 -> 7 -> 6 -> 2 -> 1) 이다. 리턴 순서를 보면 DP로 각 노드가 선택되었을 때 최댓값, 선택되지 않았을 때 최댓값으로 판단해가며 구현할 수 있다는 아이디어를 떠올리는 것이 중요한 것 같다.

 

1) DP[x][0] = 노드(x)를 선택했고, 그 밑(next) 노드는 선택할 수 없음. 따라서 그 밑(next) 노드의 DP[x][1] 값을 더해준다.

2) DP[x][1] = 노드(x)를 선택하지 않았고, 그 밑(next) 노드는 크기에 따라서 선택하거나 선택하지 않을 수 있음. 둘 중 큰 값을 더해준다.

 

3. 이렇게 상향식으로 DP를 구현할 수 있다. DP를 구성한 후에, 역추적으로 노드 번호를 출력하거나, DFS 함수 내에 노드 번호를 저장하는 방식으로 구현할 수 있다.

 

- 역추적 함수 방법

import sys
input = sys.stdin.readline

n = int(input())
d = [0]+list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
v = [0 for _ in range(n+1)]
path = []
dp = [[0, 0] for _ in range(n+1)]

for _ in range(n-1):
	a, b = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)

def dfs(idx):
	v[idx] = 1
	dp[idx][0] = d[idx]
	dp[idx][1] = 0
	for next in graph[idx]:
		if v[next] == 0:
			dfs(next)
			dp[idx][0] += dp[next][1]
			dp[idx][1] += max(dp[next][0], dp[next][1])

dfs(1)
print(max(dp[1]))
v = [0 for _ in range(n+1)]

def trace(idx, bool):
	v[idx] = 1
	if bool == 0:
		for next in graph[idx]:
			if v[next] == 0:
				trace(next, 1)
	else:
		if dp[idx][0] > dp[idx][1]:
			path.append(idx)
			for next in graph[idx]:
				if v[next] == 0:
					trace(next, 0)
		else:
			for next in graph[idx]:
				if v[next] == 0:
					trace(next, 1)
	return

trace(1, 1)
print(*sorted(path), end = ' ')

 

 

- DFS 함수 내에 번호를 저장하는 방법

import sys
input = sys.stdin.readline

n = int(input())
d = [0]+list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
v = [0 for _ in range(n+1)]
path = [[[], []] for _ in range(n+1)]
dp = [[0, 0] for _ in range(n+1)]

for _ in range(n-1):
	a, b = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)

def dfs(x):
	v[x] = 1
	dp[x][0] = d[x]
	dp[x][1] = 0
	path[x][0].append(x)
	for next in graph[x]:
		if v[next] == 0:
			temp = dfs(next)
			dp[x][0] += dp[next][1]
			dp[x][1] += max(dp[next][0], dp[next][1])
			path[x][0] += temp[1]
			if dp[next][1] > dp[next][0]:
				path[x][1] += temp[1]
			else:
				path[x][1] += temp[0]
	return path[x]

dfs(1)

if dp[1][1] > dp[1][0]:
	print(dp[1][1])
	print(*sorted(path[1][1]))
else:
	print(dp[1][0])
	print(*sorted(path[1][0]))
반응형