[코드트리] 인접한 정점 C++

문제

https://www.codetree.ai/missions/9/problems/adjacent-node?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 10001;

int n;
int weight[MAX_N];
vector<int> edges[MAX_N];
bool visited[MAX_N]={false, };

int parent[MAX_N];
int dp[MAX_N][2]; // dp[i][0]: i를 선택하지 않았을 때 최대값, dp[i][1]: i를 선택했을 때 최대값


void DFS(int x){
    for(int i=0; i<(int)edges[x].size(); ++i){
        int y = edges[x][i];
        if(visited[y]) continue;
        visited[y]=true;
        parent[y]=x;
        DFS(y);
    }

    dp[x][0]=0, dp[x][1]=weight[x];
    bool child_selected = false;

    for(int i=0; i<(int)edges[x].size(); ++i){
        int y = edges[x][i];
        if(parent[y]==x){
            // x를 선택하는 경우=자식을 선택하지 않은 경우
            dp[x][1]+=dp[y][0];

            // 자식을 선택할 것인지 말 것인지 고려
            // 자식을 선택한 게 자식을 선택하지 않은 것보다 크다면 부모선택x-자식 선택o
            if(dp[y][1] > dp[y][0]) {
                dp[x][0] += dp[y][1];
                child_selected = true;
            }
            else dp[x][0]+= dp[y][0];
        }
    }

    // 자식을 하나도 선택하지 않았다면(=모든 자식을 dp[x][0]+= dp[y][0]한 경우),
    // 가장 이득이 큰 자식 하나를 강제로 선택

    // dp[x][0]에 모든 자식을 선택하지 않는 경우(dp[y][0])를 더했기 때문에
    // 이득이 큰 자식을 선택하려면, 선택하는 자식에 대해 아래 연산을 수행해야 한다.
    // dp[x][0]=dp[x][0]-dp[y][0]+dp[y][1]

    // -dp[y][0]+dp[y][1]=max_diff가 되고, dp[x][0]과 합쳐주는 연산을 취하므로
    // dp[x][0]+=max_diff
    if(!child_selected){
        int max_diff = 0;
        for(int i=0; i<(int)edges[x].size(); ++i) {
            int y = edges[x][i];
            if(parent[y] == x) {
                max_diff = max(max_diff, dp[y][1] - dp[y][0]);
            }
        }
        dp[x][0]+= max_diff;
    }

}
int main() {
    // input
    // 정점의 수 n이 주어집니다.
    cin >> n;
    // 1번 정점부터 n번 정점까지 각 정점에 적힌 수가 번호 순서대로 공백으로 구분되어 주어집니다.
    for(int i=1; i<=n; ++i){
        cin >> weight[i];
    }
    // n-1 개의 줄에 걸쳐, 트리의 각 간선이 연결하는 두 정점의 번호가 공백으로 구분되어 주어집니다.
    for(int i=1; i<n; ++i){
        int a, b;
        cin >> a >> b;
        // 간선 연결
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    // solution
    visited[1]=true;
    DFS(1);

    // output
    cout << max(dp[1][0], dp[1][1]) << '\n';
    return 0;
}

 

모든 자식을 선택하지 않았다는 것은 "모든 자식 y가 y 노드를 선택한 결과보다 선택하지 않은 결과가 좋았다(dp[y][1]<dp[y][0])"는 것을 의미한다.

 

x노드를 선택하지 않으려면 x노드에 연결된 자식들 중 적어도 하나의 자식을 선택되어야 한다.

dp[x][0](=x노드를 선택하지 않는 경우)을 계산할 때, dp[y][1]-dp[y][0]이 가장 큰 값인 자식을 선택해야 한다.

 

왜냐하면 모든 자식이 지금 dp[y][1]<dp[y][0]인 상황인데, 노드 1의 자식 2, 3, 4가 아래와 같은 dp 값을 가지고 있다고 해보자

dp[2][1]=5, dp[2][0]=10

dp[3][1]=4, dp[3][0]=10

dp[4][1]=3, dp[4][0]=10

 

2를 선택한다면 5점을 잃고(dp[2][1]-dp[2][0]=-5),

3을 선택한다면 6점을 잃고(dp[3][1]-dp[3][0]=-6),

4를 선택한다면 7점을 잃게 된다(dp[4][1]-dp[4][0]=-7).

최대 점수를 얻기 위해서는 어떤 노드를 선택해야 하는가?

 

가장 적은 점수를 잃을 수 있는 2번 노드를 선택하는 것이 옳은 선택이 된다. 즉, -5, -6, -7 중에 최대값인 -5를 선택해야 한다는 의미이다.

max(dp[2][1]-dp[2][0], dp[3][1]-dp[3][0], dp[4][1]-dp[4][0])

 

처음 코드

아래 코드는 부모 노드를 선택하지 않은 경우 자식 노드들의 가중치를 모두 더하도록 한다.(dp[x][0]+=dp[y][1])

 

그러나 아래 그림과 같이 일부 자식만 선택해도 조건을 만족할 수 있다.

 

위 그림의 최적해를 계산하면 아래와 같은 dp 테이블이 만들어지고, max(dp[1][0], dp[1][1])=16이 정답이 된다.

 

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 10001;

int n;
int weight[MAX_N];
vector<int> edges[MAX_N];
bool visited[MAX_N]={false, };

int parent[MAX_N];
int dp[MAX_N][2]; // dp[i][0]: i를 선택하지 않았을 때 최대값, dp[i][1]: i를 선택했을 때 최대값


void DFS(int x){
    for(int i=0; i<(int)edges[x].size(); ++i){
        int y = edges[x][i];
        if(visited[y]) continue;
        visited[y]=true;
        parent[y]=x;
        DFS(y);
    }

    dp[x][0]=0, dp[x][1]=weight[x];

    for(int i=0; i<(int)edges[x].size(); ++i){
        int y = edges[x][i];
        if(parent[y]==x){
            // 선택하지 않은 정점은 1개 이상의 정점과 인접해 있어야 한다.
            // x를 선택하지 않는 경우=자식을 선택하는 경우
            dp[x][0]+=dp[y][1];
            // 선택한 정점끼리 인접해 있으면 안 된다
            // x를 선택하는 경우=자식을 선택하지 않은 경우
            dp[x][1]+=dp[y][0];
        }
    }
}
int main() {
    // input
    // 정점의 수 n이 주어집니다.
    cin >> n;
    // 1번 정점부터 n번 정점까지 각 정점에 적힌 수가 번호 순서대로 공백으로 구분되어 주어집니다.
    for(int i=1; i<=n; ++i){
        cin >> weight[i];
    }
    // n-1 개의 줄에 걸쳐, 트리의 각 간선이 연결하는 두 정점의 번호가 공백으로 구분되어 주어집니다.
    for(int i=1; i<n; ++i){
        int a, b;
        cin >> a >> b;
        // 간선 연결
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    // solution
    visited[1]=true;
    DFS(1);

    // output
    cout << max(dp[1][0], dp[1][1]) << '\n';
    return 0;
}

 

개선된 방법

해설을 보니 최대값을 더해주는 방법을 채용하면 자동으로 2번 조건이 만족되어, 최적해가 보장된다고 적혀 있었다.

• 선택한 정점끼리 인접해 있으면 안 됩니다.
• 선택하지 않은 정점은 최소 하나의 선택한 정점과 인접해 있어야 합니다.

단순히 max(dp[y][0], dp[y][1])을 선택하는 것만으로 2번 조건이 어떻게 보장되는지 이해가 어려웠다.

dp[x][0]+= max(dp[y][1], dp[y][0]);을 했을 때 모든 자식이 선택되지 않을 수도 있지 않은가?

 

이에 대한 답이 토론란에 적혀 있었다.

 

내가 이해한 대로 조금 더 쉽게 보충해보자면,

모든 자식이 선택되지 않는 경우, 1번 조건(선택한 정점끼리 인접해 있으면 안 됨)에 의해 무조건 x노드가 선택된다.

왜냐하면 모든 자식노드 y를 선택하지 않으면 연속으로 선택될 일이 없으므로 x노드를 선택하는 것이 무조건 이득이다.

 

dp[x][0]과 dp[x][1]에서 모든 자식 노드 y가 선택되지 않았다고 해보자.

dp[x][0]은 sum(every dp[y][0]) 이 될 것이고,

dp[x][1]은 sum(every dp[y][0])+weight[x]가 될 것이다.

 

weight[i]는 모두 양수이기 때문에 dp[x][0]과 dp[x][1] 중에서 더 큰 값은 dp[x][1]이 된다.

 

따라서 dp[x][0]은 다음 선택에 영향을 미치지 못하게 된다(dp[x][1]이 더 큰값이기 때문에). 

 

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 10001;

int n;
int weight[MAX_N];
vector<int> edges[MAX_N];
bool visited[MAX_N]={false, };

int parent[MAX_N];
int dp[MAX_N][2]; // dp[i][0]: i를 선택하지 않았을 때 최대값, dp[i][1]: i를 선택했을 때 최대값


void DFS(int x){
    for(int i=0; i<(int)edges[x].size(); ++i){
        int y = edges[x][i];
        if(visited[y]) continue;
        visited[y]=true;
        parent[y]=x;
        DFS(y);
    }

    dp[x][0]=0, dp[x][1]=weight[x];

    for(int i=0; i<(int)edges[x].size(); ++i){
        int y = edges[x][i];
        if(parent[y]==x){
            dp[x][1]+=dp[y][0];
            dp[x][0]+= max(dp[y][1], dp[y][0]);
        }
    }
    
}
int main() {
    // input
    // 정점의 수 n이 주어집니다.
    cin >> n;
    // 1번 정점부터 n번 정점까지 각 정점에 적힌 수가 번호 순서대로 공백으로 구분되어 주어집니다.
    for(int i=1; i<=n; ++i){
        cin >> weight[i];
    }
    // n-1 개의 줄에 걸쳐, 트리의 각 간선이 연결하는 두 정점의 번호가 공백으로 구분되어 주어집니다.
    for(int i=1; i<n; ++i){
        int a, b;
        cin >> a >> b;
        // 간선 연결
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    // solution
    visited[1]=true;
    DFS(1);

    // output
    cout << max(dp[1][0], dp[1][1]) << '\n';
    return 0;
}