BOJ 3654 - L퍼즐 (D4)

사용 알고리즘
Bipartite Matching

 

풀이

L을 가로 일자랑 세로 일자로 분리해서 생각해보자. 그럼 결국 검정색 하나를 기준으로 흰색 2개가 가로에 최대 1개, 세로에 최대 1개 붙을 수 있다. 이를 이용해 이분 그래프를 만들고 이분매칭을 해서 전체가 매칭되는지 확인하면 된다.

 

BOJ는 hopcroft-karp로 냈는데 코드가 길어서 여기서는 일반 이분매칭 코드를 올린다.

#include <bits/stdc++.h>
using namespace std;
#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 MOD2 998244353
#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 long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
ll n, m;
ll cntB,cntW;
ll a[252525], b[252525];
bool visited[252525];
vector<ll> adj[252525];
bool dfs(ll x){
    if(visited[x])return 0;
    visited[x] = 1;
    for(auto next : adj[x]){
        if(b[next]<0 or dfs(b[next])){
            a[x] = next;
            b[next] = x;
            return 1;
        }
    }
    return 0;
}
string s[505];
ll num[505][505];
void solve(){
    memset(num,0,sizeof(num));
    cin>>n>>m;
    cntB=cntW=0;
    for(int i = 0 ; i < n ; i++){
        cin>>s[i];
        for(int j = 0 ; j < m ; j++){
            if(s[i][j]=='B')num[i][j] = ++cntB;
            if(s[i][j]=='W')num[i][j] = ++cntW;
        }
    }
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            if(s[i][j] != 'W')continue;
            for(int k = 0 ; k < 4 ; k++){
                ll nx = i+"2011"[k]-'1', ny = j+"1120"[k]-'1';
                if(nx<0 or ny<0 or nx>n-1 or ny>m-1 or s[nx][ny] != 'B')continue;
                ll t = (k < 2 ? num[nx][ny]+cntB : num[nx][ny]);
                adj[num[i][j]].push_back(t);
            }
        }
    }
    memset(a,-1,sizeof(a));
    memset(b,-1,sizeof(b));
    ll ans=0;
    for(int i = 1 ; i <= cntW ; i++){
        memset(visited,0,sizeof(visited));
        ans += dfs(i);
    }
    cout<<(ans == cntW and cntB * 2 == cntW ? "YES" : "NO")<<"\n";
    for(int i = 1 ; i <= cntW ; i++)adj[i].clear();
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

이번 겨울학교 문제 중 하나였고 분명 출처가 있는 문제인 것 같아서 백준에서 플래티넘 범위에서 이분매칭 태그 달고 모든 문제를 찾아다녔는데 못 찾았다. 오늘 한 블로그의 풀이를 보다가 출처를 알게 되었는데 알고보니 다이아였고 이분매칭 태그도 안 달려있었다...