16726번 영과일 학회방

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

백트래킹 문제인줄 알아서, 백트래킹으로 풀고 제출하였는데

시간 초과가 났다. 그래서 생각해보니 배열 크기가 50*50이므로, 

하나 하나 모든 경우의 수(1*2 크기를 가로로 놓는 경우, 세로로 놓는 경우 등)를 살펴보기에는 너무 오래 걸린다.

그래서, 이분 매칭을 공부한 다음에 다시 풀고 제출하였더니 맞았다. 

더 공부해야겠다.

참고로, 시간 초과가 뜬 코드도 확실한 정답 코드가 아니다.

시간 초과가 뜨고, 정답도 아닌(테스트 케이스가 조차 틀린) 코드도 올려본다. 

물론 틀린 테스트 케이스는 아직 안 찾아봤다.

추가적으로,

정답 코드에서 상하좌우 모두 매칭을 신경써줘야 한다. 

따라서, point vector에 모두 넣는다.

<시간 초과 코드, 백트래킹> - 테스트 케이스 조차 틀린 코드일 확률 99.9999%

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int N = 0, M = 0, total = 0, two = 0, one = 0, var = 0, result = 0;
 
int dy[2] = { 0, 1 };
int dx[2] = { 1, 0 };
 
int xcnt = 0;
 
char Map[51][51];
 
bool visit[51][51] = { false, };
 
bool One[51][51] = { false, };
 
int one_calc()
{
    int ret = 0;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (visit[i][j] || Map[i][j] == 'X') continue;
 
            ++ret;
        }
    }
 
    return ret;
}
 
void BackTracking(int pos)
{
    if (pos == (N*M - xcnt) / 2)
    {
        result = min(result, two + one_calc());
 
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            for (int k = 0; k < 2; k++)
            {
                int y = i + dy[k];
                int x = j + dx[k];
 
                if (x < 0 || x >= M || y < 0 || y >= N || visit[y][x] || visit[i][j] || Map[i][j] == 'X' || Map[y][x] == 'X') continue;
 
                visit[i][j] = true;
                visit[y][x] = true;
                two += 1;
 
                BackTracking(pos + 1);
 
                two -= 1;
                visit[i][j] = false;
                visit[y][x] = false;
            }
        }
    }
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    result = 987654321;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> Map[i][j];
 
            if (Map[i][j] == 'X') ++xcnt;
        }
    }
 
    BackTracking(0);
 
    printf("%d\n", result);
 
    return 0;
}

<정답 코드, 이분 매칭>

#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 51
 
int R = 0, C = 0;
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
int number[MAX][MAX] = { 0, };
 
char Map[MAX][MAX];
 
vector<int> point, Left, Right;
 
vector<vector<int> > v;
 
vector<bool> visit;
 
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()
{    
    Left = vector<int>(R*C + 1, -1);
    Right = vector<int>(R*C + 1, -1);
 
    int ret = 0;
 
    for (int i = 0; i < point.size(); i++)
    {
        visit = vector<bool>(R*C + 1, false);;
 
        if (DFS(i)) ++ret;
    }
 
    return ret / 2;
    // 2개씩 짝이므로, 나누기 2를 해준다.
}
 
int main(void)
{
    int xcnt = 0;
 
    scanf("%d %d", &R, &C);
 
    v = vector<vector<int> >(R*C + 1);
 
    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;
 
            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 < 4; 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]);    
            }
        }
    }
 
    int two = bm();
 
    int one = R*C - 2*two - xcnt;
 
    printf("%d\n", two + one);
 
    return 0;
}