[백준-1949] 우수마을

그래프 + dp 문제 이다.

이 문제를 풀기 이전에 dp와 dfs 를 같이 사용해서 생각하는 방법을 기를 수 있어야 한다. 일단 해당 문제는 top-down dp 방식으로 풀이할 수 있다.

예를 들어 7 부터 tree 를 순회한다고 할 때,

• 7번째 마을을 우수마을로 선정하는 경우
• 7번째 마을을 우수마을로 선정하지 않는 경우

2가지의 경우로 DP 상태를 선정할 수 있다. 또한 7번째 마을을 우수마을로 선정하기 위해서는 7번째 마을과 연결된 마을들이 선정되지 않는 경우를 알아야 하고, 7번째 마을을 우수마을로 선정하지 않기 위해서는 상관이 없다.

이를 이용해서 dp 로직을 구할 수 있다.

• 특정 마을이 선정되는 경우 = (자식 마을이 선정되지 않은 경우의 합) + 특정 마을의 인원수
• 특정 마을이 선정되지 않는 경우 = (자식 마을의 두 경우의 최대값의 합)

이를 dfs 로 구현하기 위해서는 재귀 느낌의 방식으로 잘 짜임새있게 코딩해야 한다.

즉, 맨 마지막 leaf 노드는 (자기 자신의 인원수, 0) 를 반환한다는 방향성을 가지고 쭉 탐색해주어야 한다. 그 부분이 다음의 dfs 함수 코드이다. (말이 이상하지만 패스..)

void dfs(int x, vector<vector<int>> &v) {
    for (int i = 0; i < v[x].size(); i++) {
        int nx = v[x][i];
        if (check[nx]) continue;
        check[nx] = 1;
        dfs(nx, v);
        dp[x][0] += dp[nx][1];
        dp[x][1] += max(dp[nx][0], dp[nx][1]);
    }
    dp[x][0] += arr[x];
    return;
}

 

 

 

 

#define _CRT_SECURE_NO_WARNINGS

#include <string>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>

#define MAX_INT 1000000000
using namespace std;

typedef pair<int, int> pii;
int arr[10001];
int check[10001];
int dp[10001][2];

void dfs(int x, vector<vector<int>> &v) {
    for (int i = 0; i < v[x].size(); i++) {
        int nx = v[x][i];
        if (check[nx]) continue;
        check[nx] = 1;
        dfs(nx, v);
        dp[x][0] += dp[nx][1];
        dp[x][1] += max(dp[nx][0], dp[nx][1]);
    }
    dp[x][0] += arr[x];
    return;
}
int main() {
    int n;
    cin >> n; 
    vector<vector<int>> v(n+1);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
    int a, b;
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    check[1] = 1;
    dfs(1, v);

    printf("%d", max(dp[1][0], dp[1][1]));
    return 0;
}

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

1949번: 우수 마을