BOJ 32070 - 색깔 모으기 (P5)

24년 KOI 2차 초등부 3번, 중등부 2번이다.

체감상 중등부는 2번, 3번, 4번 난이도가 다 똑같은데 이게 맞나?

그건 그렇고 이 문제 풀이가 정말 재밌어서 풀이를 써보겠다.

 

먼저 $A_i$ -> $B_i$을 간선으로 하는 그래프를 생각해보자. 만약 $A$가 순열이라면(위에 놓여 있는 공의 색이 모두 다름) 이 그래프는 여러 개의 사이클로 이루어져 있을 것이다. 그리고 이 사이클대로 따라가면서 공을 옮기다 보면 그 사이클의 공을 모두 같은 색끼리 모을 수 있으며, 이 때 옮기는 횟수는 (사이클 크기) + 1이다. (사이클 크기가 1인 경우는 예외로 옮길 필요가 없다.) 따라서 답은 저 (사이클 크기) + 1을 모든 사이클에 대해서 더해준 값이 된다.

그럼 $A$가 순열이 아니라면 어떻게 될까? 이 경우에는 이동이 불가능한 경우가 생길 수 있다. 이동이 불가능할 조건은 어떤 컴포넌트가 사이클도 아니고 DAG도 아니면 된다. (즉, 한 정점에서 시작해서 모든 정점을 방문할 수 없음) 또한 각 정점의 (indegree) + (outdegree) = 2이므로 사이클도 아니고 DAG가 아닐 조건은 한 컴포넌트에 (outdegree) = 2인 정점이 2개 이상인 것이라는 것도 알 수 있다. (1개라면 DAG가 되고, 0개이면 사이클이 된다)

이제 남은 것은 DAG에서의 최소 이동 횟수이다. 이건 (indegree) + (outdegree) = 2를 다시 한번 이용하면 쉽게 알 수 있다. 저 성질 때문에 DAG인 컴포넌트는 반드시 아래 그림과 같이 생겼다.

양갈래의 크기가 각각 x,y인 DAG

시작 노드에서 양갈래로 흩어졌다가 마지막에 모이는 형태이다. 이 경우 시행 횟수는 다음과 같다.

1: 시작 노드에 해당하는 색 2개를 빈 상자에 옮긴다(2회). (indegree = 2이므로 이 색깔의 공 2개는 반드시 상자의 위에 있다)

2: 양갈래 각각을 그래프를 따라가면서 마지막 상자 바로 전까지 옮긴다(x+y회).

3: 마지막 노드에 해당하는 색을 한 곳에 모은다(1회).

즉 x+y+3회가 든다. x+y+2가 DAG의 크기이므로 결국 DAG크기 + 1만큼 이동해야 한다.

그런데 사이클도 (사이클 크기) + 1만큼 이동해야 하므로 종류에 관계없이 (컴포넌트 크기) + 1을 해주면 된다. (다시 말하지만 크기 = 1은 예외 처리를 해줘야 한다)

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef __int128_t lll;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
ll p[202020];
ll outd[202020];
ll cnt[202020];
ll n;
ll find(ll x){
    if(p[x]<0)return x;
    return p[x] = find(p[x]);
}
void merge(ll x, ll y){
    x = find(x), y = find(y);
    if(x==y)return;
    cnt[x] += cnt[y];
    p[x] += p[y];
    p[y] = x;
    if(cnt[x]>1){
        cout<<"-1";
        exit(0);
    }
}
int main(){
    fast;
    cin>>n;
    vector<P> edge;
    for(int i = 0 ; i < n ; i++){
        ll a,b; cin>>a>>b; outd[a]++; edge.push_back({a,b});
    }
    for(int i = 1 ; i <= n ; i++)if(outd[i]==2)cnt[i] = 1;
    memset(p,-1,sizeof(p));
    for(auto [a,b] : edge)merge(a,b);
    ll ans = 0;
    for(int i = 1 ; i <= n ; i++)if(p[i]<-1)ans += abs(p[i])+1;
    cout<<ans;
}

여담으로 기여에다가 재밌다고 써놨는데 똑같이 재밌다고 써놓은 기여가 2개나 더 있다. 역시 갓문제