#2213 트리의 독립집합

출처: https://www.acmicpc.net/problem/2213

2213번: 트리의 독립집합

트리의 독립집합을 구하는 문제인데 연결 돼 있는 정점 또는 노드들을 연속으로 선택하지 않으면 되는 문제이다.

재귀를 활용한 dp를 통해 구하였다.

그래서 노드를 선택 할지 않할지 어떤 노드인지를 구분하기위한 memo 자료구조는

struct(선택, 선택x) memo[노드 개수] 와같이 선정하였다.

 

알고리즘 점화식은 다음과 같다.

 

알고리즘 점화식 핵심

현재 선택한 노드라면 += (다음 노드 선택하지 않는다.)

현재 노드 선택하지 않은 노드라면 +=MAX(다음 노드는 선택 or 다음 노드 선택 x)

 

종료조건

visit 배열을 만들어 방문처리

 

노드를 찾는 알고리즘

memo는 1.선택했다, 2.안했다 가 있는데 만약 1>2이면 해당 노드를 선택한 경우에 해당한다.

예제같은 경우는 memo[1].1<memo[1].2 이여서 1번 노드는 선택하지 않았다.

그리고 시작점은 1이므로 1에서부터 쭉쭉 퍼져나가는 식으로 노드들을 찾아주면 된다.

추가로 이전에 선택이 됐던 노드들이 중복으로 푸쉬되는 것을 방지해야한다.

 

소스코드