백준 16726 / C++

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

16726번: 영과일 학회방

 

[ 풀이 ] 

예제 생긴것부터 플로우 문제네요. n제한도 작으니...

격자판을 1*2 와 1*1로 채울 수 있습니다.  최소개수가 필요하니 1*2들을 최대한 써줘야 합니다. 

격자를 체스판처럼 컬러링한 후 색이 다른걸 이분매칭을 돌려주면 됩니다. 

이분매칭으로 최대한 찾은 결과가 k라고 하면, 'X'를 제외한 면적에서 2k가 빠집니다. 그럼 나머지 S-2k는

1*1로 채워야 하므로 S-2k개가 필요합니다. 따라서 답은 S-k가 됩니다. 

 

[ Code ] 

#include<bits/stdc++.h>
using namespace std;
char a[55][55];
vector<int>g[55 * 55];
int par[55 * 55], vis[55*55];
vector<int>v;

int match(int x) {
    for (int nx : g[x]) {
        if (vis[nx])continue;
        vis[nx] = 1;
        if (!~par[nx] || match(par[nx])) {
            par[nx] = x;
            return 1;
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    int area = n * m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'X') area--;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if ((i + j) & 1 || a[i][j] == 'X')continue;
            v.push_back(m * i + j);
            if (i - 1 >= 0 && a[i - 1][j] != 'X') {
                g[m * i + j].push_back(m * (i - 1) + j);
            }
            if (i + 1 < n && a[i + 1][j] != 'X') {
                g[m * i + j].push_back(m * (i + 1) + j);
            }
            if (j - 1 >= 0 && a[i][j - 1] != 'X') {
                g[m * i + j].push_back(m * i + j - 1);
            }
            if (j + 1 < m && a[i][j + 1] != 'X') {
                g[m * i + j].push_back(m * i + j + 1);
            }
        }
    }
    int ans = 0;
    memset(par, -1, sizeof(par));
    for (int i : v) {
        memset(vis, 0, sizeof(vis));
        ans += match(i);
    }
    cout << area - ans;
}