백준 32583 - Watchdogs (C++)

문제

• 문제 링크

  
   BOJ 32583 - Watchdogs 
  

• 문제 요약

$N$개의 도시로 이루어진 마을 코코르코프 속에서 $K$마리의 쥐가 이동한다. 구체적으로 $K$개의 도시쌍 $(A, B)$가 주어질 때 다음을 만족하는 도시 $C$ 중 적어도 한 곳에 고양이를 배치하려고 한다.



$|d(C, A)−d(C, B)| ≤ 1$

도시 $C$는 $A$와 $B$ 사이의 경로에 포함된다.


한 고양이는 여러 마리의 쥐를 처리할 수 있으며 처음 배치된 자리에 머무를 때, $K$마리의 쥐를 감시하기 위해 최소 몇 마리의 고양이를 배치해야 할지 구해보자.


• 제한

TL : $5$ sec, ML : $1024$ MB




$2 ≤ N ≤ 10^5$

$0 ≤ K ≤ 10^5$

알고리즘 분류

• 트리 (trees)
• 최소 공통 조상 (lowest common ancestor)
• 다이나믹 프로그래밍 (dynamic programming)
• 트리에서의 다이나믹 프로그래밍 (dynamic programming on trees)

풀이

트리에서 임의의 두 정점 $(u, v)$에 대해 중간에 위치하는 정점은 $LCA$를 이용해 $O(logN)$에 쉽게 구해줄 수 있다.

$LCA(u, v)$를 구한 뒤 깊이가 더 낮은 정점에서 $\frac{d(u, v)}{2}$만큼 리프팅을 해주면 되는데, 보다 일반화된 문제를 풀어보고자 한다면 BOJ 13511 - 트리와 쿼리 2 를 먼저 풀고 오도록 하자.

---

한편, 문제의 정의에 따르면 $d(u, v)$가 짝수일경우 중간 도시가 하나로 특정되어 바로 고양이를 배치하면 쉽게 해결할 수 있다. 문제는 $d(u, v)$가 홀수일 때인데, 이 경우 문제의 조건을 만족하는 중간 도시가 둘이 되어 버린다.

두 중간 도시가 간선 하나로 이어져있는 상황에서 둘 중 한 곳에만 고양이를 배치하면 된다는 점에 주목해보자.

이 상황에 놓인 간선들만을 모아서 새로이 트리를 구성해주면 이 문제는 골드 중반에 포진해있는 전형적인 트리 DP 문제로 바라볼 수 있게 된다.

이 문제에서는 최솟값이지만 최댓값을 구해야 하는 이 문제 가 비슷하지 않을까 싶다.

---

새롭게 구성된 트리에서 각 도시는 고양이가 배치되거나, 배치되지 않은 상태를 가질 수 있으므로 다음과 같이 정의해줄 수 있다.

$dp[i][j]$ $:$ $i$번 도시의 고양이 배치 여부가 $j$일 때의 답.

이어서 $now → nxt$를 잇는 간선을 보고 있을 때 각 상태 전이는 다음 두가지로 분류할 수 있다.

$dp[now][1] = min(dp[nxt][1], dp[nxt][0])$

$dp[now][0] = dp[nxt][1]$

각 도시에 대해 중복 배치가 일어나지 않도록 고양이 배치 여부를 기록할 배열을 함께 운용하는 것이 편하다. 자세한 흐름은 아래 코드를 참고하자.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
vector <vector <int>> dp(N, vector <int>(2, -1));
vector <int> Gr[N], Gr_[N];
 
int dep[N], flag[N];
int n, k, pdp[N][18];
 
void Input()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i{}; ++i < n;)
    {
        int u, v; cin >> u >> v;
        Gr[u].push_back(v);
        Gr[v].push_back(u);
    }
}
void LCAInit(int now, int depth)
{
    dep[now] = depth;
    for(int nxt : Gr[now])
        if(!dep[nxt])
        {
            pdp[nxt][0] = now;
            LCAInit(nxt, depth + 1);
        }
}
void TableDP()
{
    for(int j(1); j < 18; j++)
        for(int i{}; i < n; i++)
            pdp[i][j] = pdp[pdp[i][j - 1]][j - 1];
}
int Lifting(int u, int diff)
{
    for(int i{}; diff; diff >>= 1, i++)
        if(diff & 1)
            u = pdp[u][i];
 
    return u;
}
int getLCA(int u, int v)
{
    u = Lifting(u, dep[u] - dep[v]);
    if(u == v)
        return u;
 
    for(int i(17); ~i; i--)
        if(pdp[u][i] ^ pdp[v][i])
        {
            u = pdp[u][i];
            v = pdp[v][i];
        }
 
    return pdp[u][0];
}
int coverDP(int prev, int now, int is)
{
    auto& cur(dp[now][is]);
    if(~cur) return cur;
 
    cur = is;
    if(is) cur -= flag[now];
 
    for(int nxt : Gr_[now])
        if(nxt ^ prev)
        {
            if(is) cur += min(coverDP(now, nxt, 0), coverDP(now, nxt, 1));
            else cur += coverDP(now, nxt, 1);
        }
 
    return cur;
}
void getAns(int ans = 0)
{
    while(k--)
    {
        int u, v; cin >> u >> v;
        if(dep[u] < dep[v])
            swap(u, v);
 
        int lca(getLCA(u, v)), dis(dep[u] + dep[v] - 2 * dep[lca]);
        int target(Lifting(u, dis >> 1));
 
        if(dis & 1)
        {
            Gr_[target].push_back(pdp[target][0]);
            Gr_[pdp[target][0]].push_back(target);
        }
        else if(!flag[target])
        {
            flag[target] = 1;
            ans++;
        }
    }
 
    for(int i{}; i < n; i++)
    {
        sort(Gr_[i].begin(), Gr_[i].end());
        Gr_[i].erase(unique(Gr_[i].begin(), Gr_[i].end()), Gr_[i].end());
    }
 
    for(int i{}; i < n; i++)
        if(Gr_[i].size() && !~dp[i][0])
            ans += min(coverDP(i, i, 0), coverDP(i, i, 1));
 
    cout << ans;
}
int main()
{
    Input();
    LCAInit(0, 1);
    TableDP();
    getAns();
}

comment

끝