https://www.acmicpc.net/problem/1949
1. 분류
Tree
Dynamic Programming
2. 풀이
Tree DP라고 불리는 유형의 문제이다.
문제의 3가지 조건에 맞춰 DP 배열을 업데이트 해주자.
풀이 전략은 다음과 같다.
- DP 테이블 정의
- DFS로 노드 탐색
- 부모 노드 방문 중 자식 노드에서 얻을 수 있는 최고의 점수를 업데이트
1. DFS로 각 노드를 계속 타고 내려간다.
1) 각 노드에 방문할 때마다 일반 마을/우수 마을의 기본값을 설정한다.
- dp[isGood][idx]로 정의한다.
- isGood = 0이면 일반, 1이면 우수마을이다.
- 일반 마을이면 값은 0, 우수 마을의 경우 해당 마을의 인구 수로 초기화한다.
2) 자식 노드를 탐색한다.
- 일반적인 DFS와는 다르게 방문했던 노드를 다시 방문하면 안된다.
2. 현재 노드의 자식 노드에서 얻을 수 있는 값을 DP 테이블에 반영한다.
1) 현재 마을이 우수 마을인 경우 자식 노드는 무조건 일반 마을이어야 한다.
- dp[1][cur] += dp[0][next];
2) 현재 마을이 일반 마을일 경우, 자식 노드는 일반 마을/우수 마을이 될 수 있다.
- dp[0][cur] += MAX(dp[0][next], dp[1][next]);
3. 갱신하다 보면 최상단 노드 데이터가 정답이 된다.
1) dp[0][1], dp[1][1] 중 큰 값을 정답으로 출력한다.
예제 입력으로 그림 예시를 들어보았다.
7
1000 3000 4000 1000 2000 2000 7000
1 2
2 3
4 3
4 5
6 2
6 7
아래 그림에서 각 노드의 숫자가 의미하는 숫자는 위부터 차례대로 노드 번호, dp[0](일반), dp[1](우수마을)이다.
dp[0]은 하위 노드의 dp[0], dp[1] 중 큰 값을 더하고,
dp[1]은 하위 노드의 dp[0]을 더해준다.
3. 소스코드
#include <iostream>
#include <vector>
#define MAX(a, b) (a) > (b) ? (a) : (b)
using namespace std;
vector<int> cnt;
vector<int> node[10001];
bool visit[10001] = { false, };
int dp[2][10001] = { 0, };
// Tree DP 구성
void dfs(int cur) {
if (visit[cur]) {
return;
}
// 초기값 정의
// dp[0][idx] : 일반 마을
// dp[1][idx] : 우수 마을
visit[cur] = true;
dp[0][cur] = 0;
dp[1][cur] = cnt[cur];
for (int next : node[cur]) {
if (visit[next]) continue;
dfs(next);
dp[0][cur] += MAX(dp[0][next], dp[1][next]);
dp[1][cur] += dp[0][next];
}
}
int main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
cnt.push_back(0);
for (int i = 0, input; i < n; i++) {
cin >> input;
cnt.push_back(input);
}
for (int i = 0, a, b; i < n; i++) {
cin >> a >> b;
node[a].push_back(b);
node[b].push_back(a);
}
dfs(1);
cout << (MAX(dp[0][1], dp[1][1])) << "\n";
return 0;
}
'알고리즘' 카테고리의 다른 글
2021 KAKAO BLIND RECRUITMENT 3번[검색 순위] 해설 (0) | 2021.02.23 |
---|---|
2021 KAKAO BLIND RECRUITMENT 2번[메뉴 리뉴얼] 해설 (0) | 2021.02.18 |
알고리즘 Repository (0) | 2019.12.09 |
BOJ [7576] 토마토 (0) | 2017.11.15 |
BOJ [10660] 구간 합 구하기 5 (0) | 2017.11.15 |