[BOJ 18313] Cave Paintings

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

18313번: Cave Paintings

Tag : DSU, Tree DP

 

문제요약

이차원 격자에서 서로 다른 칸 a,b가 min(a의 높이, b의 높이)인 정점만을(막혀있지 않은 칸) 지나는 경로가 존재할 때 a 또는 b에 물을 채우면 다른 한쪽에도 차오른다. 이 때 서로 다른 물이 차오르는 형태의 경우의 수를 구하라.

 

풀이

1. 같은 y좌표를 갖고 y이하인 정점을 통해 도달할 수 있는 정점끼리는 모두 한 정점으로 치환한다. 

2. 두 정점 (x,y), (x,y-1)가 모두 '.'이라면 이를 잇는 간선을 만든다.

위의 과정을 통해 만든 그래프는 트리의 집합인 포레스트다.

 

따라서 각 컴포넌트(트리)마다 트리디피를 통해 경우의 수를 각각 구할 수 있으며 이를 모두 곱한 것이 답이 된다. 

\(dp_i:=\)i에 물을 흘려보내는 경우의 수 + i는 물을 흘리지 않고 i의 서브트리에 물을 흘려보내는 경우의 수

와 같이 정의하면 매우 간단한 Tree DP를 통해 답을 구할 수 있다. 

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

struct DSU{
    int n;
    vector<int>pa;
    DSU(int _n):n(_n){pa.resize(n+1);iota(all(pa),0);}
    int find(int a){return a==pa[a]?a:(pa[a]=find(pa[a]));}
    void merge(int a,int b){pa[find(b)]=find(a);}
    int chk(int a,int b){return find(a)==find(b);}
};

int N,M;
int indegree[1010101];
char v[1010][1010];
vector<int>g[1010101];
int idx(int i,int j){return (i-1)*M+(j-1)+1;}
const ll MOD=1000000007;
ll ans=1;

void print(int x){cout<<"("<<((x-1)/M)+1<<","<<((x-1)%M+1)<<")";}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>N>>M;
    DSU *a=new DSU(N*M);
    DSU *b=new DSU(N*M);
    for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)cin>>v[i][j];
    for(int i=N;i>=1;i--){
        map<int,vector<int>>mp;
        for(int j=1;j<=M;j++){
            if(v[i][j]=='.')mp[a->find(idx(i,j))].pb(b->find(idx(i,j)));
            if(v[i][j]=='.' and v[i][j-1]=='.')b->merge(idx(i,j),idx(i,j-1));
        }
        for(auto&[key,val]:mp){
            for(int j=1;j<siz(val);j++){
                b->merge(val[j],val[j-1]);
                //print(val[j]),cout<<"->",print(val[j-1]),cout<<endl;
            }
        }
        for(int j=1;j<=M;j++){
            if(v[i][j]=='.' and v[i-1][j]=='.')a->merge(idx(i,j),idx(i-1,j));
            if(v[i][j]=='.' and v[i][j-1]=='.')a->merge(idx(i,j),idx(i,j-1));
        }
    }
//    cout<<b->chk(idx(2,2),idx(2,3))<<endl;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(v[i][j]=='.' and v[i-1][j]=='.'){
                indegree[b->find(idx(i,j))]++;
                g[b->find(idx(i-1,j))].pb(b->find(idx(i,j)));
            }
        }
    }
    vector<int>root;
    for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){
        if(v[i][j]=='.' and indegree[b->find(idx(i,j))]==0)root.pb(b->find(idx(i,j)));
    }
    function<ll(int,int)>f=[&](int x,int dep=0)->ll{
        ll ret=1;
        compress(g[x]);
        for(auto&i:g[x]){
            ret=ret*f(i,dep+1)%MOD;
        }
        return (ret+1)%MOD;
    };
    compress(root);
    for(auto&s:root)ans=ans*f(s,0)%MOD;
    cout<<ans<<endl;
}