반응형
https://www.acmicpc.net/problem/1949
1949번: 우수 마을
N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며,
www.acmicpc.net
1. 문제설명
인접한 노드 두개가 우수마을이 되면 안된다.
그리고 자신이 우수마을이 아니라면 인접한 노드 중 적어도 하나가 우수마을이 되어야한다.
문제를 해결하기 위해
노드를 재귀적으로 탐색해야한다.
현재 노드가 우수마을인 경우와 우수마을이 아닌 경우를 나눈다.
그리고 현재 노드가 우수마을인 경우에는 다음 노드는 무조건 우수마을이면 안된다.
현재 노드가 우수마을이 아닌 경우에는 다음 노드는 우수마을이거나 우수마을이 아닐 수 있다.
이 때
현재 우수마을이 아닌데 다음 마을도 우수마을이 아닌 경우 문제가 생길 수 있다고 생각했다.
예를 들어 세개의 노드가 다 우수마을이 아닌 경우라면 문제의 조건에 맞지 않다.
하지만 다음 코드와 같이 재귀적으로 탐색하면서 최댓값을 계속 넘겨주다보면
모든 마을이 우수마을이 아닌 경우는 남지 않아서 괜찮다.
최댓값만 남기기 때문에 모든 마을이 우수마을이 아닌 경우는 살아남을 수 없다.
2.문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
#define MX 10001
int N, people[MX], dp[MX][2];
bool vis[MX];
vector<int> adj[MX];
void DFS(int node){
dp[node][0] = 0;
dp[node][1] = people[node];
vis[node] = 1;
for(int i=0; i<adj[node].size(); i++){
int nx = adj[node][i];
if(vis[nx]) continue;
DFS(nx);
dp[node][0] += max(dp[nx][0], dp[nx][1]);
dp[node][1] += dp[nx][0];
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N;
for(int i=1; i<=N; i++){
cin >> people[i];
}
for(int i=1; i<N; i++){
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
DFS(1);
cout << max(dp[1][0], dp[1][1]) << '\n';
return 0;
}반응형
'Algorithm > problem' 카테고리의 다른 글
| 백준 2533 : 사회망 서비스(SNS) - 트리 DP, C++ (0) | 2022.10.03 |
|---|---|
| 백준 15681번 : 트리와 쿼리 - DFS , C++ (0) | 2022.10.02 |
| [백준] 4256번 : 트리 - 재귀 (0) | 2022.10.02 |
| 백준 5639번 : 이진 검색 트리 - 트리 구현 후위 순회 C++ (0) | 2022.10.01 |
| 백준 2250번 : 트리의 높이와 너비 - 트리, C++ (0) | 2022.10.01 |
