2213 트리의 독립집합

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

2213번: 트리의 독립집합

 

이 문제를 풀기전에 2533번  https://kimximya.tistory.com/54 을 풀었어서 스무스 했다

트리 DP에 역추적 하면 풀린다, 골드1 짜리 문제는 아닌 듯 하다

 

트리 DP 방법론

- 트리를 짠다

- int[][] DP = new int[N+1][2]  짜리 디피테이블을 만든다

- dfs를 돌린다

- DP[x][0] 은 집합에 x를 포함하지 않았다는 의미

- DP[x][1] 은 집합에 x를 포함했다는 의미

- DP[x][1] = W[x] 로 일단 설정해준다

- 그 후 자식 정점에 대해서 DP[x][0] += Math.max( DP[자식][0], DP[자식][1] ) 을 해준다

- DP[X][1] 은, 자기 자신이 포함됐으므로 자식은 포함되면 안된다, 그러므로

- DP[X][1] += DP[자식][0]

- DFS가 끝나고 DP[루트][0], DP[루트][1] 중 더 큰걸 출력해준다

 

역추적 방법론

- 우선순위 큐를 만든다

- 탑다운으로 조건 검사를 할꺼다

- dfs 함수 파라미터에 isPossible 불린 판별 인자를 추가해준다

- DFS를 또 돌린다

- 첫 시작의 isPossible 은 true다

- 만약 isPossible == true 일 경우, 해당 정점에서의 DP테이블을 조사한다

-  DP[x][1] > DP[x][0] 이라면, 즉, 해당 정점을 독립집합에 넣는게 값이 더 크다면

- 우선순위 큐에 x를 추가하고 다음 dfs에 인자를 false로 넣어준다

- 더 작다면 아무 것도 안한다

- isPossible == false 라면 다음 dfs 다음 인자를 true 로 넣어준다

- 대충 이렇게 한다음 우선순위큐 출력해주면 독립집합 정렬되서 나옴

 

https://github.com/KimximyaFan/Random-Defense/blob/main/C0049.java