백준 3654 L퍼즐

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

 

클래스 9 문제

이쁜 풀이 하나와 다른 풀이 두 가지가 있다.

모든 풀이에서 공통되는 관찰은 각 검은 칸이 상하 중 정확히 하나, 좌우 중 정확히 하나의 하얀 칸을 골라야 한다는 점이다. 

 

sol 1:

"정확히 하나" 조건에서 매칭 냄새가 난다. 각 검은 칸을 상하 칸, 좌우 칸으로 분할하면 모든 검은 칸과 하얀 칸을 일대일대응시킬 수 있는지 여부로 답을 구할 수 있고, 이분 매칭을 돌리면 문제를 풀 수 있다. 크기가 크니 호프크로프트-카프 알고리즘을 사용해야 한다.

#include <bits/stdc++.h>
using namespace std;
 
struct HK {
    vector<int> l, r, chk, lev;
    vector<vector<int>> G;
    int L, R;
    HK(int L, int R) : L(L), R(R), G(L+1), l(L+1), r(R+1), lev(L+1), chk(L+1) {}
    void addEdge(int a, int b) {
        G[a].push_back(b);
    }
    int bfs(){
        queue<int> q;
        for (int i = 1; i <= L; i++){
            if (!l[i]){
                lev[i] = 0;
                q.push(i);
            }
            else lev[i] = -1;
        }
        int ret = 0;
        while (q.size()){
            int v = q.front();
            q.pop();
            for (int i : G[v]){
                if (!r[i]) ret = 1;
                else if (lev[r[i]] == -1){
                    lev[r[i]] = lev[v]+1;
                    q.push(r[i]);
                }
            }
        }
        return ret;
    }
    int dfs(int v){
        chk[v] = 1;
        for (int i : G[v]){
            if (!r[i] or (!chk[r[i]] and lev[r[i]] == lev[v]+1 and dfs(r[i]))){
                r[i] = v;
                l[v] = i;
                return 1;
            }
        }
        return 0;
    }
    int maxMatch(){
        int ret = 0;
        while (bfs()){
            fill(chk.begin(), chk.end(), 0);
            for (int i = 1; i <= L; i++){
                if (!l[i] and dfs(i))
                    ret++;
            }
        }
        return ret;
    }
};
 
char C[505][505];
int id[505][505];
 
void solve(){
    int N, M, L = 0, R = 0;
    cin >> N >> M;
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= M; j++){
            cin >> C[i][j];
            if (C[i][j] == 'W') id[i][j] = ++R;
            else if (C[i][j] == 'B') id[i][j] = ++L;
        }
    }
    if (L*2 != R){
        cout << "NO\n";
        return;
    }
    HK A(L*2, R);
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= M; j++){
            if (C[i][j] == 'B'){
                if (C[i-1][j] == 'W') A.addEdge(id[i][j]*2-1, id[i-1][j]);
                if (i+1 <= N and C[i+1][j] == 'W') A.addEdge(id[i][j]*2-1, id[i+1][j]);
                if (C[i][j-1] == 'W') A.addEdge(id[i][j]*2, id[i][j-1]);
                if (j+1 <= M and C[i][j+1] == 'W') A.addEdge(id[i][j]*2, id[i][j+1]);
            }
        }
    }
    cout << (A.maxMatch() == R ? "YES\n" : "NO\n");
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

 

sol 2:

상하 중 하나, 좌우 중 하나 모두 둘 중 하나를 고르는 조건이니 2-SAT 쪽으로도 생각할 수 있다고 한다. 검은 정점에서는 둘 중 정확히 하나만 고르기를, 흰색 정점에서는 넷 중 정확히 하나만 고르기를 모델링해야 한다.

 

sol 3:

이분 매칭 풀이에서 모든 정점이 매칭되어야 한다는 강한 조건이 붙으니 쉬운 풀이가 있을 것 같다. 상/하, 좌/우처럼 둘 중 하나만 선택되어야 하는 관계를 둘을 잇는 간선으로 표현하자. 이렇게 만들어진 그래프에서 모든 간선마다 끝점 중 하나씩 겹치지 않게 선택할 수 있는지 여부가 원래 그래프에서 모든 정점이 매칭되어야 한다는 조건과 동치이며, 끝점 하나씩 겹치지 않게 선택할 수 있음은 모든 컴포넌트에서 정점의 수와 간선의 수가 같음과 동치이다. 따라서 그래프를 구성한 뒤 유니온파인드, dfs 등으로 문제를 풀 수 있다.