(C++) - 백준(BOJ) 1949번 : 우수 마을

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

1949번: 우수 마을

tree를 만들고 dfs를 수행하며 top down dp로 해결한 문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

 1. 마을마다 주민수를 입력받아 일차원 배열에 저장합니다.

 

 2. 인접리스트로 무방향 그래프를 만들어 줍니다. 이를 graph라는 vector형 변수에 저장합니다.

 

 3.  루트노드에서 출발하여 문제에서 나온 규칙을 계속해서 지켜가며 트리의 아래로 내려간다면 결국 답이 나온다는 줄기를 생각해야 합니다. 또한 각 마을(노드)는 우수마을로 선정될 경우, 선정되지 않을 경우의 두 가지 상태가 존재합니다. 따라서 최소의 규칙을 지키며 내려가기 위해, 두 상태를 표현하기 위해 이차원 배열 d라는 변수를 만들어줍니다. 이 배열은 d[노드번호][우수마을선정여부]의 의미를 담고 있으며 우수마을 선정이 되지 않았다면 d[x번 마을][0], 되었다면 d[x번 마을][1]이 됩니다.

 

📔 풀이과정

 1. 1번 마을부터 시작해 dfs를 수행합니다. 트리 구조의 특성상 사이클이 없기 때문에 어떤 노드에서 시작해도 상관없습니다. 하지만 편의를 위해 1번노드를 임의의 시작마을로 정했습니다. 

 

 1-1. 현재마을 x의 상태를 갱신해줍니다. d[x][0]은 우수마을이 아니므로 주민을 포함시킬 필요가 없습니다. 따라서 0으로 저장합니다. d[x][1]은 우수마을이므로 주민을 포함해야합니다. 알맞게 저장해줍니다.

 

 1-2. x의 인접마을을 확인합니다. 이는 next마을이라고 정의합니다. 이미 들렀던 마을이라면 continue 아니라면 방문해줍니다(dfs 호출). 이로써 각 마을의 초기값들이 다 저장이 되었습니다. 다 저장이 되었다면 말단 노드(마을)의 정보로 부터 부모 노드를 갱신하면서 올라갑니다. x가 우수마을이라면 문제에서의 2번 규칙에 의해 인접마을은 모두 일반 마을이어야 합니다. 따라서 d[x][0] += d[next][0](모든 인접마을)이라는 공식이 성립합니다. x가 일반마을이라면 인접마을이 일반 또는 우수마을일 수 있습니다. 따라서 d[x][1] += max(d[next][0],d[next][1])입니다. 

 

📔 정답출력

 루트노드 즉 시작노드(마을)을 출발점으로 잡았으니 최종 갱신된 값은 d[1][0], d[1][1]에 저장되어있습니다. 이들 중 최댓값을 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, ck[10001];
int peoplePerVilage[10001];
vector <int> graph[10001];
int d[10001][2]; //0은 일반 , 1은 우수마을

void dfs(int x){
    if(ck[x]) return;
    ck[x] = 1;
    d[x][0] = 0;
    d[x][1] = peoplePerVilage[x];
    for(auto next : graph[x]){
        if(ck[next]) continue;
        dfs(next);
        d[x][1] += d[next][0];
        d[x][0] += max(d[next][0], d[next][1]);
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> peoplePerVilage[i];
    }

    for(int i = 1,u,v; i <= n - 1; i++){
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    dfs(1);
    cout << max(d[1][0], d[1][1]);
}