[2414번] 게시판 구멍 막기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최소 버텍스 커버

2. 네트워크 플로우 :: http://www.crocus.co.kr/741

3. 최대 유량

4. 이분 매칭 :: http://www.crocus.co.kr/499

이 문제 또한 최소 버텍스 커버로 해결할 수 있다.

일단 이 문제를 풀기 전에, [1867번] 돌멩이 제거 :: http://www.crocus.co.kr/749 를 먼저 풀어보자.

최소 버텍스 커버 문제임을 확인하면 이분 매칭으로 접근 할 수 있게 된다.

위의 돌멩이 문제와는 다른게 게시판이 구멍이 뚫려있지 않은 부분은 테이핑 할 수 없기에 함부로 밀면 안된다.

따라서 위의 기준처럼 행을 기준으로 구멍을 넘버링 한다.

대신 이때 연속되지 않으면 카운트를 올려서 넘버링 해야 한다.

열 또한 마찬가지로 넘버링 해준다.

이제 그래프로 나타내면 다음과 같이 되는데

여기서 푸른색 동그라미의 의미가 뭐냐면, 

행의 1번으로 열의 1번을 테이핑

행의 3번으로 열의 3,4,5번을 테이핑

행의 4번으로 열의 2,3,4번을 테이핑

열의 4번으로 행의 2,3,4,5번을 테이핑 한다는 의미이다.

이분 매칭이니 최대 유량 관점으로(capacity :: 1)도 해석 할 수 있고, 일단 이 문제를 어떻게 최소 버텍스 커버로 볼 수 있느냐가 제일 중요한 것 같다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
 
#define MAX_N 650
using namespace std;
 
int n, m;
int aMatch[MAX_N];
int bMatch[MAX_N];
vector<int> adj[MAX_N];
 
int visit[MAX_N];
int visitCnt;
 
char map[51][51];
int cArr[51][51];
int rArr[51][51];
 
bool chkNum[MAX_N];
 
int num = 1;
 
bool dfs(int a)
{
    if (visit[a] == visitCnt)
        return false;
 
    visit[a] = visitCnt;
 
    for (int i = 0; i < adj[a].size(); i++)
    {
        int b = adj[a][i];
 
        if (bMatch[b] == -1 || dfs(bMatch[b]))
        {
            bMatch[b] = a;
            aMatch[a] = b;
 
            return true;
        }
        
    }
    return false;
}
 
int bipartiteMatch()
{
    memset(aMatch, -1, sizeof(aMatch));
    memset(bMatch, -1, sizeof(bMatch));
 
    int ans = 0;
 
    for (int start = 1; start <= num; start++)
    {
        visitCnt++;
        ans += dfs(start);
    }
 
    return ans;
}
int main()
{
    scanf("%d %d", &n, &m);
 
    for(int i = 0; i < n; i ++)
        scanf("%s", map[i]);
 
 
    // 행 먼저 넘버링
    for (int i = 0; i < n; i++)
    {
        if(chkNum[num])
            num++;
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] == '*')
            {
                cArr[i][j] = num;
                chkNum[num] = true;
            }
            else if(map[i][j] == '.')
                if (chkNum[num])
                    num++;
        }
    }
 
    int tmp = num;
    num = 1;
    memset(chkNum, false, sizeof(chkNum));
    // 열 넘버링
    for (int i = 0; i < m; i++)
    {
        if (chkNum[num])
            num++;
        for (int j = 0; j < n; j++)
        {
            if (map[j][i] == '*')
            {
                rArr[j][i] = num;
                chkNum[num] = true;
            }
            else if (map[j][i] == '.')
                if (chkNum[num])
                    num++;
        }
    }
    /*
    cout << endl;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cout << cArr[i][j] << " ";
        cout << endl;
    }
    cout << endl;
    cout << endl;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cout << rArr[i][j] << " ";
        cout << endl;
    }
    cout << endl;
    */
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (cArr[i][j] != 0)
                adj[cArr[i][j]].push_back(rArr[i][j]);
 
    if (tmp > num)
        num = tmp;
    printf("%d", bipartiteMatch());
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>