백준 2414 : 게시판 구멍 막기

문제 링크

쾨닉의 정리를 이용한 문제이다.

먼저 테이프는 겹쳐도 되고, 구멍이 뚫려있지 않은 부분은 테이프를 붙일 수 없다는 문제의 조건에 따라서 붙여야 하는 테이프의 크기를 최대로 해서 테이프를 붙일 가로 테이프, 세로 테이프를 정리한다.

그렇다면 테이프는 최대 n*m만큼 나오므로 이중for문을 통해서 edge를 만들어 줄 수 있고, 이 때 edge는 테이프 끼리 공통부분이 있는경우에 만들어 준다. 테이프의 크기는 최대로 만들었기 때문에 가로테이프끼리는 간선이 만들어지지 않고, 세로끼리도 마찬가지이다. 따라서 주어진 그래프는 이분 그래프가 된다.

여기서 *가 있는 지점에 대해서 가로 혹은 세로 테이프 중 적어도 하나가 선택돼야 한다는 것을 알 수 있고, 여기서 최소 버텍스 커버의 개념을 생각해 볼 수 있다. 아까 문제에서 주어진 그래프는 이분 그래프임을 찾았으므로, 쾨닉의 정리를 이용해서 이분매칭을 통해 문제를 해결할 수 있다.

쾨닉의 정리/최소 버텍스 커버

비슷한 문제로는 1867번 돌멩이 제거 문제가 있다.
문제 링크

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const ll INF = 1LL<<60;
const int MAX = 1e9;

int n,m;

struct hor{
    int r,from,to;

    hor(int _r,int _from,int _to):r(_r),from(_from),to(_to)
    {

    }
};

struct vert{
    int c,from,to;

    vert(int _c,int _from,int _to):c(_c),from(_from),to(_to)
    {

    }
};

bool interact(const hor& h,const vert& v)
{
    return h.from <= v.c && v.c <= h.to && v.from <= h.r && h.r <= v.to;
}

vector<string> table;
vector<hor> hortape;
vector<vert> verttape;
vector<vector<int>> edge;
vector<int> amatch;
vector<int> bmatch;
int hsize;
int vsize;
vector<bool> visit;

bool dfs(int cur)
{
    if(visit[cur]) return false;
    visit[cur] = true;

    for(auto next : edge[cur])
    {
        if(bmatch[next] == -1 || dfs(bmatch[next]))
        {
            amatch[cur] = next;
            bmatch[next] = cur;
            return true;
        }
    }
    return false;
}

int Bipartite()
{
    amatch = vector<int>(hsize + vsize,-1);
    bmatch = vector<int>(hsize + vsize,-1);

    int ret = 0;

    for(int i = 0;i<hsize;i++)
    {
        visit = vector<bool>(hsize,false);

        if(dfs(i)) ret++;
    }

    return ret;
}

int main()
{
    ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin>>n>>m;

    table = vector<string>(n);

    for(int i = 0;i<n;i++)
    {
        cin>>table[i];
    }

    for(int i = 0;i<n;i++)
    {
        int from = -1;
        int to;

        for(int j = 0;j<m;j++)
        {
            if(table[i][j] == '*')
            {
                if(from == -1) from = j;
                to = j;
            }
            else
            {
                if(from != -1) hortape.emplace_back(i,from,to);
                
                from = -1;
            }
        }

        if(from != -1) hortape.emplace_back(i,from,to);
    }

    for(int j = 0;j<m;j++)
    {
        int from = -1;
        int to;

        for(int i = 0;i<n;i++)
        {
            if(table[i][j] == '*')
            {
                if(from == -1) from = i;
                to = i;
            }
            else
            {
                if(from != -1) verttape.emplace_back(j,from,to);
                from = -1;
            }
        }

        if(from != -1) verttape.emplace_back(j,from,to);
    }

    hsize = hortape.size();
    vsize = verttape.size();

    edge = vector<vector<int>>(hsize+vsize);

    for(int i = 0;i<hsize;i++)
    {
        for(int j = 0;j<vsize;j++)
        {
            if(interact(hortape[i],verttape[j]))
            {
                edge[i].push_back(j+hsize);
                edge[j+hsize].push_back(i);
            }
        }
    }

    cout<<Bipartite();
    return 0;
}