PS/백준 문제 풀이

[백준 1949번] 우수 마을 (C++)

홀든콜필드 2025. 4. 22. 01:08
728x90

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

 

이전에 비슷한 문제의 유형을 풀어본적이 있기 때문에 트리에서 다이나믹 프로그래밍 문제라는 것을 알 수 있었다.

 

사실 말은 거창하지만 DFS + DP 와 다를 것이 없다. 문제를 살펴보자

 

  1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
  2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
  3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

뭔가 조건이 많아보이는데 사실 1,2번을 만족하면 3번은 자동으로 될 수밖에 없다. 1번의 조건으로 최대한 많은 우수마을을 만들어야하기 때문에 당연히 우수마을이 아닌 마을들은 인접한 마을에 우수마을이 있을 수 밖에 없다.

 

그리고 어떤 정답이 있을지 알아보자.

 

 

여기서 같은 색의 별표들이 정답이 될 수 있는 경우의 수 들이다. 이 경우의 수는

(N combination N / 2) / 2 와 같고 N은 1만이기 때문에 완전탐색은 불가능하다.

 

Dynamic Programming

 

DP[i][1] = i번 노드를 선택했을 때 이 노드가 우수마을일 경우 우수마을의 최대 인구수

DP[i][0] = i번 노드를 선택했을 때 이 노드가 우수마을이 아닐 경우 우수마을의 최대 인구수

Value[i] = i번 마을의 인구수

 

이렇게 구성해보자.  각 노드는 반드시 우수마을이거나 아닌 경우의 수 밖에 없기 때문에 우선 타당해보인다.

 

그렇다면 점화식은 어떻게 새워야할까? 

 

위 그림에서 1번에서 출발한다고 해보자. 

 

1번 노드의 인접인 2번으로 이동한다. 

1번 노드의 인구수는 100, 2번 노드의 인구수는 200이라 해보자.

 

2번노드는 더이상 자식노드가 없기 때문에 자기 자신을 우수마을로 지정하거나 없거나 둘중하나다.

그러므로 DP[2][1] = 200, DP[2][0] = 0

 

다시 1번으로 돌아가자. 

1번은 2번을 우수마을로 정했을 경우 나를 우수마을로 지정할 수 없고, 나를 우수마을로 지정하면 내 인구수를 사용해야한다.

 

아하... 점화식이 보이는 것 같다.

 

DP[i][1] = DP[i][1] + DP[j][0]

-> 1번노드를 우수마을로 선정하면 반드시 이전것은 우수마을이 지정되지 않는다.

 

DP[i][0] = MAX(DP[j][0], DP[j][1]) 

-> 1번노드가 우수마을이 아니라면 그냥 큰 수를 더하면 된다.

 

그리고 1번 노드입장에서는 왼쪽을 다녀왔으니 오른쪽도 가야한다. 그러므로 자식노드들의 값들을 모두 더해준다.

 

vector<int> tree[MAX];
int value[MAX];
int dp[MAX][2];

bool visited[MAX];

int dfs(int n){
    dp[n][1] = value[n];
    dp[n][0] = 0;

    visited[n] = true;

    for(int i = 0; i < tree[n].size(); i++){
       
        int next = tree[n][i];

        if(visited[next]) continue;
        visited[next] = true;

        dfs(next);

        dp[n][1] += dp[next][0];
        dp[n][0] += max(dp[next][0], dp[next][1]);

    }
    //cout << n << ' ' << dp[n][1] << ' ' << dp[n][0] << endl;

    return max(dp[n][1], dp[n][0]);
}

 

그렇다면 DFS는 이렇게 정의될 수 있다. 

 

시뮬레이션을 돌려보자.

 

 

예제를 살펴보면 5개의 노드가 있고 각 DP는 초기엔 자기자신을 선택한것과 아무것도 선택하지 않은 것으로 0으로 초기화되어 있다.

먼저 정답부터 살펴보고 가면 2, 4, 5를 선택해 800의 인구수를 만드는 것이 최적해일 것이다.

 

또 파란색으로 쓴 숫자는 이 DFS에서 도달하는 노드의 순서이다.

 

 

2번노드에 도달했다가 1번으로 돌아오면서  

dp[n][1] += dp[next][0];
dp[n][0] += max(dp[next][0], dp[next][1]);

 

점화식에 따라 값이 갱신되었다. 

 

한번에 살펴보자. 이제 4번으로 이동한 후 3번을 갱신했다. 그리고 5번을 갔다가 3번을 갱신했다.

현재까지만 살펴보면 3번을 우수마을로 선정하지 않고 4,5번을 우수마을로 선정해 쓰는 것이 적절해보인다.

 

그리고 1번으로 돌아가 1번을 다시 한 번 갱신한다. 

 

1번을 우수마을 선택한다면 3번노드를 우수마을로 선정하지 않은 600을 더하게 될 것이고

1번을 우수마을 선택하지 않는다면 3번 노드를 우수마을이던 아니던 큰 값을 더하게 되어 600을 더한다.

 

결론적으로 아까 처음 예상했던 답 처럼 2, 4, 5를 선택해 800이 정답이 되었다. 

 

그리고 DP[1][0] 이 정답이 됨으로서 1번이 우수마을이 아닐 때 정상적으로 정답인 것 까지 확인했다.

 

처음에 말했듯이 트리에서 다이나믹 프로그래밍은 DFS를 DP 최적화하는 것과 크게 다르지 않다.

 

DP의 기본인 큰 문제를 작은 문제로 쪼갤 수 있고, 반복적으로 탐색해야하는 것을 메모이제이션으로 한번 방문 후에는 다시 방문하지 않아도 된다는 것을 다시 상기하자.

 

#include <iostream>
#include <vector>
#define MAX 10001
using namespace std;

int N;

vector<int> tree[MAX];
int value[MAX];
int dp[MAX][2];

bool visited[MAX];

int dfs(int n){
    dp[n][1] = value[n];
    dp[n][0] = 0;

    visited[n] = true;

    for(int i = 0; i < tree[n].size(); i++){
       
        int next = tree[n][i];

        if(visited[next]) continue;
        visited[next] = true;

        dfs(next);

        dp[n][1] += dp[next][0];
        dp[n][0] += max(dp[next][0], dp[next][1]);

    }
    //cout << n << ' ' << dp[n][1] << ' ' << dp[n][0] << endl;

    return max(dp[n][1], dp[n][0]);
}

int main(){
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> value[i + 1];
    }

    for(int i = 0; i < N - 1; i++){
        int a, b; cin >> a >> b;

        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    cout << dfs(1) << '\n';
}