[백준][C++] 1949 우수 마을

www.acmicpc.net/problem/1949

1949번: 우수 마을

 

 

 

알고리즘 종류

트리

다이나믹 프로그래밍

 

 

 

사고 과정

앞서 풀어본 이 문제와 이 문제를 통해 아주 쉽게 풀 수 있었습니다. 독립집합 문제입니다.

 

독립집합이 되기 위해서는 A마을이 선택되면 연결된 다른 마을들은 선택되면 안됩니다. 반대로, A마을이 선택되지 않으면 연결된 다른 마을들은 선택되거나 선택되지 않아야 됩니다. 이러한 문제를 독립집합이라고 하는 것 같습니다. 따라서 DP로 풀면 될 것 같습니다.

 

조건은 다음과 같습니다.

    - A가 선택되면, 연결된 다른 노드들은 선택할 수 없다.

    - A가 선택되지 않으면, 다른 노드들은 선택되거나 선택되지 않아도 된다.

 

가장 먼저 Root가 될 노드를 찾기로 했습니다. 연결된 간선이 1개면 됩니다. 그리고 DP를 수행하여 최대 독립집합을 구했습니다. 마지막으로 최대 독립집합의 노드들을 구하기 위해서 Root부터 시작하여 DP의 크기를 비교하면서 노드들을 찾았습니다. 구체적인 내용은 아래 코드를 보면 쉬울 것 입니다.

 

과정을 이미지로 나타내면 아래와 같습니다. 빨간색은 가중치, 화살표는 DP가 수행되는 방향 입니다. 편의상 1000자리를 10의 자리로 대체하여 가중치를 빨간색으로 나타냈습니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int n;
 
int dp[10001][2];
int isVisited[10001];
 
vector<vector<int> > edges; // 노드 연결된 간선 정보  
vector<int> weights; // 노드의 가중치  
vector<int> nodes; // 노드에 간선이 몇 개 연결되어 있는지. 간선이 1개 있는 노드에서 DP 시작하기 위해서  
 
 
// 최대 독립집합의 크기 구하기  
void dfs(int node){
    isVisited[node] = 1;
    dp[node][0] = 0;
    dp[node][1] = weights[node];
    
    for(int i=0; i<edges[node].size(); i++){
        int conn_node = edges[node][i];
        if(isVisited[conn_node]) continue;
        
        dfs(conn_node);
        
        dp[node][0] += max(dp[conn_node][0], dp[conn_node][1]);
        dp[node][1] += dp[conn_node][0];
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> n;
    edges.resize(n+1);
    weights.resize(n+1);
    nodes.resize(n+1);
    
    int w;
    for(int i=1; i<=n; i++){
        cin >> w;
        weights[i] = w;
    }
    
    int u, v;
    while(cin >> u >> v){
        
        edges[u].push_back(v);
        edges[v].push_back(u);
        
        nodes[u]++;
        nodes[v]++;
    }
    
    // 간선이 1개 있는 노드 찾기  
    int root;
    for(int i=1; i<=n; i++){
        if(nodes[i] == 1) root = i;
    }
    
    // 최대 독립집합 구하기  
    dfs(root);
    
    cout << max(dp[root][1], dp[root][0]) << endl;
}
 

 

 

 

시행착오