1014번 컨닝

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

이분 매칭 문제이다. 다른 분의 이분 매칭에 대한 개념과 코드를 보면서 코드를 구현하였다.

문제 그림에 주어진 4방향만 신경 쓸 것이 아니라,

컨닝을 할 수 있는 그리고 컨닝을 '당하는' 것까지 신경써줘야 한다.

2에서 4를 컨닝한다고 치자.(2 → 4)

하지만, 4 → 2를 안 해주면, 둘이 매칭이 안 되어 원하는 답을 구할 수가 없게 된다.

추가적으로, 

컨닝을 '하는', '당하는' 두 분류로 나누어서 구현해야하기 때문에 

0 1 2 3

4 5 6 7

8 9 10 11

짝수일 때만(0, 2, 4, 6, 8, 10) point vector에 저장하도록 했다.

즉, 단순 위와 아래에 있는 관계는 매칭이 되면 안 된다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
#define MAX 12
 
char Map[MAX][MAX];
 
int number[MAX][MAX] = { 0, };
 
int Left[MAX * MAX + 1] = { 0, };
int Right[MAX * MAX + 1] = { 0, };
 
int dy[6] = { -1, -1, 0, 0, 1, 1 };
int dx[6] = { -1, 1, -1, 1, -1, 1 };
 
vector<int> v[MAX * MAX + 1];
 
vector<int> point;
 
bool visit[MAX * MAX + 1] = { false, };
 
bool DFS(int start)
{
    if (visit[start]) return false;
 
    visit[start] = true;
 
    for (auto next : v[start])
    {
        if (Right[next] == -1 || DFS(Right[next]))
        {
            Left[start] = next;
            Right[next] = start;
 
            return true;
        }
    }
 
    return false;
}
 
int bm()
{
    fill(Left, Left + MAX * MAX + 1, -1);
    fill(Right, Right + MAX * MAX + 1, -1);
 
    int ret = 0;
 
    for(auto i : point)
    {
        memset(visit, false, sizeof(visit));
 
        if (DFS(i)) ++ret;
    }
 
    return ret;
}
 
void init()
{
    memset(visit, false, sizeof(visit));
    memset(number, 0, sizeof(number));
 
    for (int i = 0; i < MAX * MAX + 1; i++)
    {
        if (!v[i].empty()) v[i].clear();
    }
 
    if (!point.empty()) point.clear();
 
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            Map[i][j] = 'x';
        }
    }
}
 
int main(void)
{
    int T = 0, R = 0, C = 0;
 
    scanf("%d", &T);
 
    while (T--)
    {
        init();
 
        int xcnt = 0;
 
        scanf("%d %d", &R, &C);
 
        int cnt = 0;
 
        for (int i = 0; i < R; i++)
        {
            for (int j = 0; j < C; j++)
            {
                cin >> Map[i][j];
 
                if (Map[i][j] == 'x') ++xcnt;
 
                if (j % 2 == 0) point.push_back(cnt);
                
                number[i][j] = cnt++;
            }
        }
 
        for (int i = 0; i < R; i++)
        {
            for (int j = 0; j < C; j++)
            {
                if (Map[i][j] == 'x') continue;
 
                for (int k = 0; k < 6; k++)
                {
                    int y = i + dy[k];
                    int x = j + dx[k];
 
                    if (y < 0 || y >= R || x < 0 || x >= C || Map[y][x] == 'x') continue;
 
                    v[number[i][j]].push_back(number[y][x]);
                }
            }
        }
        
        printf("%d\n", R*C - xcnt - bm());
    }
 
    return 0;
}