[Python3] 2213 트리의 독립집합 - 골드 1

• 2023.2.22 포스팅 기준 solved.ac 문제 등급 : 골드 1
• 단계별로 풀어보기 -> 트리에서의 동적계획법
• 알고리즘 분류
  • 다이나믹 프로그래밍
  • 트리
  • 트리에서의 다이나믹 프로그래밍

 

<링크>
https://www.acmicpc.net/problem/2213

2213번: 트리의 독립집합

시간제한	메모리제한
2 초	128 MB

 

---

<문제>
그래프 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>

7
10 30 40 10 20 20 70
1 2
2 3
4 3
4 5
6 2
6 7

<예제 출력 1>

140
1 3 5 7

 

---

<풀이 접근>

이 문제는 트리에서 DFS를 통해 Leaf 노드를 찾고, 이들로부터 해당 노드를 집합에 포함 할지, 안할지를 나눠 DP배열에 가중치를 저장하며 부모 노드를 따라 트리를 올라가면 된다. 다만, 이후의 back tracking을 위해 특정 부모 노드를 집합에 포함하지 않는 경우 어떤 자식 노드들이 최대독립집합에 포함될 수 있는지를 기록하며 DFS를 진행해야 한다.

DFS가 끝나면 트리의 Root 노드에 최대독립집합의 가중치가 저장되고, 최대독립집합의 성분 노드를 판별하는 back tracking 과정은 BFS로 구현할 수 있다.

우선, 입력 데이터를 받고 배열을 초기화하는 과정을 간략히 소개하겠다. 주석의 설명으로도 충분히 이해 되시리라 생각한다.

import sys
input = sys.stdin.readline

n = int(input())

# 트리의 각 노드 별 가중치를 vertice 배열에 저장한다. 편의상 인덱스 번호 1부터 사용한다.
vertice = [0] + [*map(int, input().split())]

# 각 노드별로 간선이 주어지면 어느 노드로 갈 수 있는지를 edge 안에 리스트로 저장한다.
# 즉, dic[1]은 1번 노드에서 갈 수 있는 노드들을 담은 리스트이다.
edge =  [[] for _ in range(n+1)]

# dfs 처리 중 동일 노드의 재방문 방지를 위한 visited 배열.
visited = [False]*(n+1)

# dp배열에 가중치를 저장한다. i번째 노드에 대해 dp[i][0]은 해당 노드를 포함하지 않는 경우이고,
# dp[i][1]은 해당 노드를 포함하는 경우이므로 미리 가중치를 넣어준다.
dp = [[0, vertice[i]] for i in range(n+1)]

# dp[i][0]의 경우, 해당 노드의 어떤 자식 노드들을 독립집합에 포함 할지를 select[i]에 저장한다.
select = [[] for _ in range(n+1)]

# 주어진 간선 정보를 dic에 저장.
for a,b in [[*map(int, line.split())] for line in sys.stdin.readlines()]:
    edge[a].append(b)
    edge[b].append(a)

 

 

다음으로 DFS 과정을 보자. 

# DFS과정을 1번 노드부터 시작한다. 임의로 정한 Root노드이고 edge의 간선 정보를 양방향으로 저장했으므로,
# visited 배열을 사용해 재방문을 방지해야 한다.

def dfs(prev, cur):
    visited[cur] = True
    for node in edge[cur]:
        if not visited[node]:
            dfs(cur, node)
            # cur노드를 독립집합에 포함하지 않는 경우를 위해, 자식노드인 node의 가중치 중 최대인 것의 인덱스를 선별한다.
            # 그리고 이 idx를 cur노드를 포함하지 않는 부분-독립집합의 가중치에 더해준다.
            # 모든 트리의 가중치가 결정된 후 백트래킹을 위해 select배열에 자식노드 node의 idx번째 가중치가 필요함을 기록한다.
            idx = max([0, 1], key = lambda i: dp[node][i])
            select[cur].append([node, idx])
            dp[cur][0] += dp[node][idx]
            dp[cur][1] += dp[node][0]
    return
    
dfs(0, 1)

트리의 한 노드가 자식노드를 셋 이상 가질 경우에 대비해 for문을 통해 자식노드들을 탐색하도록 작성했다. 
DFS는 1번 노드부터 시작하고, 자식노드로 진입할 때 자신이 부모노드임을 알리기 위해 prev인자에 스스로를 전달한다.

다음으로 백트래킹 과정을 보자.

# res[0]에는 최대독립집합의 가중치를, res[1]에는 최대독립집합에 속하는 노드를 기록한다.
res = [0,[]]

# 아래부터 백트래킹을 위한 BFS를 구현한다. 반복문으로 작성하였다.
stage = [] #stage가 BFS의 각 단계(층)를 담당한다. 

# 1번 노드의 가중치를 보고 포함 여부를 결정한다.
# stage에 [1,0]을 넣는 의미는, [1번노드, 독립집합에 포함되지 않음]이다.
if dp[1][0] > dp[1][1]:
    res[0] = dp[1][0] 
    stage.append([1,0])
# 마찬가지로 dp[1][1]이 더 클 경우, [1,1]을 stage에 넣는다.
else :
    res[0] = dp[1][1]
    stage.append([1,1])

# 아래부터 BFS를 실행한다. 1번 노드부터 시작한다.
# 독립집합에 부모노드가 포함되지 않을 때 어느 자식노드가 포함되는지를 이미 select배열에 기록했음을 이용한다.
visited = [False]*(n+1)
visited[1] = True
while stage:
    next_stage = []
    while stage:
        cur, sel = stage.pop()
        visited[cur] = True
        if sel:
            res[1].append(cur)
            next_stage += [[c, 0] for c in edge[cur] if not visited[c]]
        else:
            next_stage += select[cur]
    stage = next_stage

이렇게 되면 res[0]에는 최대독립집합의 가중치가 기록되고, res[1]에는 최대독립집합의 성분 노드들이 모두 기록된다.
마지막으로 정렬하여 출력하면 된다.

아래는 전체 소스코드이다.

import sys
input = sys.stdin.readline

n = int(input())
vertice = [0] + [*map(int, input().split())]
edge = [[] for _ in range(n+1)]
visited = [False]*(n+1)
dp = [[0, vertice[i]] for i in range(n+1)]
select = [[] for _ in range(n+1)]
for a,b in [[*map(int, line.split())] for line in sys.stdin.readlines()]:
    edge[a].append(b)
    edge[b].append(a)

def dfs(prev, cur):
    visited[cur] = True
    for node in edge[cur]:
        if not visited[node]:
            dfs(cur, node)
            idx = max([0, 1], key = lambda i: dp[node][i])
            select[cur].append([node, idx])
            dp[cur][0] += dp[node][idx]
            dp[cur][1] += dp[node][0]
    return


dfs(0, 1)
res = [0,[]]
stage = []
if dp[1][0] > dp[1][1]:
    res[0] = dp[1][0] 
    stage.append([1,0])
else :
    res[0] = dp[1][1]
    stage.append([1,1])

visited = [False]*(n+1)
visited[1] = True
while stage:
    next_stage = []
    while stage:
        cur, sel = stage.pop()
        visited[cur] = True
        if sel:
            res[1].append(cur)
            next_stage += [[c, 0] for c in edge[cur] if not visited[c]]
        else:
            next_stage += select[cur]
    stage = next_stage

print(res[0])
print(*sorted(res[1]))

---

<마무리>
트리의 Leaf노드부터 가중치를 쌓아 올려 최대독립집합의 총 가중치를 구하는 것은 어렵지 않았으나, 집합에 포함되는 성분 노드를 어떻게 전달해야 할 지 고민이 되었다. DFS과정 중 마지막 단계인 Root노드에의 복귀 전 까지는 최대독립집합에 어떤 노드가 포함될지 알 수 없다. 그래서 어떤 부모노드가 포함되지 않을 때 특정 자식노드를 포함하는것이 더 큰 가중치를 얻는지 혹은 아닌지를 select 배열에 계속 저장하면서 DFS에서 복귀하도록 했다. 사실상 최대독립집합에 속하는 정점을 요구하는 것이 이 문제의 핵심이 아니었나 싶다.