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

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

 

이 문제를 풀고난 후, 독립 집합이라는 새로운 개념을 배웠다. 이를 정리하기 위해 기록한다.

 

용어 정리

• 독립 집합(Independent Set) : 그래프에서 서로 연결되지 않은(인접하지 않은) 정점들의 집합
• 최대 가중치 독립 집합(Maximum Weight Independent Set) : 그래프의 여러 정점 중 서로 인접하지 않은 정점들을 선택하되, 선택된 정점들의 가중치(weight)의 합이 가장 커지는 집합
• 극대 독립 집합(Maximal Independent Set) : 독립 집합이면서, 집합에 정점을 추가하면 더 이상 독립성을 유지할 수 없는 상태의 집합
• 최대 독립 집합 (Maximum Independent Set): 정점의 개수가 가장 많은 독립 집합

 

풀이

 

문제에 세가지 조건이 있다.

1. 우수 마을 주민 수 합이 최대 → 최대 가중치 독립 집합
2. 인접한 두 마을을 동시에 우수 마을로 뽑을 수 없음 (우수 마을끼리 인접 불가) → 독립 집합 조건
3. 우수 마을이 아닌 마을은 적어도 하나의 우수 마을과 인접해야 함

조건 3 때문에 “우수하지 않은 마을은 반드시 우수한 마을과 인접해야 한다.”를 고려해야 할 것 같지만, 이 문제에선 주민 수가 자연수라서 고려하지 않아도 된다. 즉, 1번과 2번 조건을 만족하면 자동으로 3번 조건도 만족하게 된다.

 

1번과 2번 조건을 만족하는 독립집합 $S$(주민 수 합이 최대인 독립집합)가 있고, 이 집합이 조건 3을 어긴다고 해보자.

그러면 어떤 마을 $u$는

• 우수 마을이 아니다. ($u \notin S$)
• 인접한 우수 마을이 없다.

$u$는 $S$의 어떤 정점과도 인접하지 않으므로 $\{u\} \cup S$ 도 여전히 독립집합이 된다.

그런데 주민 수는 양수이므로, $u$를 $S$에 추가하면 합은 반드시 증가하게 된다. 그러면 $S$의 합은 최대가 아니므로 모순이 발생한다.

따라서 $S$는 조건 3을 자동으로 만족하게 된다.

 

이를 토대로 간단하게 $DP$식을 설계할 수 있다.

• $dp[$우수마을 여부 $0$ or $1][$정점 $u$$]$ : 우수마을 여부에 따른 정점 u 서브트리에서 얻는 최대 주민 수 합

1. u를 우수 마을로 선택하면, 자식은 우수 마을 X
   \[
   dp[1][u] = weight(u) + \sum_{v \in child(u)} dp[0][v]
   \]
2. u를 우수 마을로 선택하지 않으면, 자식은 우수 마을 선정/비선정 중 최댓값 선택
   \[
   dp[0][u] = \sum_{v \in child(u)} max(dp[0][v], dp[1][v])
   \]

$dfs$로 간단하게 트리 $dp$를 작성하면 된다.

 

풀이 1

 

처음 풀었을 때, 조건 3을 고려해서 풀었기 때문에 코드가 복잡하게 구현되었다.

 

현재 정점이 우수 마을이 아닐 경우, 자식들 중에는 적어도 1개는 우수 마을이 있어야 해서, 자식들 중 우수 마을이 없는 경우 강제로 1개를 우수 마을로 만들도록 설계했다. 이 때 최소한의 손해를 보고 우수 마을로 만들어야 한다.

 

정답 코드

C++17

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

int dp[2][10001];
vector<int> cnt;
vector<vector<int>> adj;

// 현재 위치, 우수 여부, 이전 마을
int dfs(int cur, bool best, int prev) {
  if (dp[best][cur] != -1) return dp[best][cur];
  dp[best][cur] = best ? cnt[cur] : 0;
  int nonBest = 0, gap = 0;
  for (auto next : adj[cur]) if (next != prev) {
    if (best) {
      dp[best][cur] += dfs(next, 0, cur);
    } else {
      int v1 = dfs(next, 0, cur), v2 = dfs(next, 1, cur);
      if (v1 > v2) nonBest++;
      dp[best][cur] += max(v1, v2);
      gap = max(gap, max(v1, v2) - min(v1, v2));
    }
  }
  if (!best && nonBest == sz(adj[cur])) {
    dp[best][cur] -= gap;
  }
  return dp[best][cur];
}

void solve() {
  memset(dp, -1, sizeof(dp));
  int n; cin >> n;
  cnt.resize(n + 1); adj.resize(n + 1);
  for (int i = 1; i <= n; i++) cin >> cnt[i];
  for (int i = 0; i < n - 1; i++) {
    int x, y; cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  cout << max(dfs(1, 0, 1), dfs(1, 1, 1));
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}

 

풀이 2

 

이 풀이가 본문의 풀이를 반영한 것이다. 확실히 구현량이 적어진 것을 볼 수 있다.

 

정답 코드

C++17

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

int dp[2][10001];
vector<int> cnt;
vector<vector<int>> adj;

void dfs(int cur, int parent) {
  dp[1][cur] = cnt[cur];
  for (auto next : adj[cur]) if (next != parent) {
    dfs(next, cur);
    dp[0][cur] += max(dp[0][next], dp[1][next]);
    dp[1][cur] += dp[0][next];
  }
}

void solve() {
  int n; cin >> n;
  cnt.resize(n + 1); adj.resize(n + 1);
  for (int i = 1; i <= n; i++) cin >> cnt[i];
  for (int i = 0; i < n - 1; i++) {
    int x, y; cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  dfs(1, 0);
  cout << max(dp[0][1], dp[1][1]);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}