비숍2


작성일 : 2017-01-21 04:43:18
조회수 : 728



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


비숍이 놓인 자리를 기준으로 왼쪽 대각선, 오른쪽 대각선은 다른 비숍을 둘 수 없습니다. 그러므로 비숍을 놓을 수 있는 자리를 기준으로 왼쪽 대각선, 오른쪽 대각선에 각각의 id를 부여한 뒤, 해당 자리의 왼쪽 대각선과 오른쪽 대각선을 그래프로 연결 시킵니다.


이 때 조심할 것은, 대각선 id의 최댓값은 100*100 칸의 체스칸에 체크무늬로 장애물이 놓여 있을 때 5000까지 가능하다는 점입니다. 인접 행렬을 통해 v[5000][5000] 칸의 배열을 잡는 것 보다는, 2차원 벡터를 활용한 인접 리스트를 이용하는 것이 좋습니다.


각 자리에 대해 왼쪽 대각선, 오른쪽 대각선의 id를 그래프로 연결 시킨 다음 보면, 결국 이 그래프에서 최고로 매칭시킬 수 있는 대각선의 수가 비숍을 놓을 수 있는 수가 되므로, 최대 이분 매칭을 찾으면 정답을 도출할 수 있습니다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

int n, m, ans, p, b[101][101], id[2][101][101];
vector<vector<int> >g;
vector<int> match;
vector<bool> visited;

bool mbm(int n)
{
    if (visited[n]) return false;
    visited[n] = true;
    for (auto it : g[n])
    {
        if (match[it] == -1 || mbm(match[it]))
        {
            match[it] = n;
            return true;
        }
    }
    return false;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y;

        cin >> x >> y;
        b[x][y] = true;
    }

    for (int i = 0; i < 2; i++)
        for (int x = 1; x <= n; x++)
            for (int y = 1; y <= n; y++)
            {
                if (!b[x][y] && !id[i][x][y])
                {
                    id[i][x][y] = ++p;
                    int tx = x, ty = y, dir = !i ? -1 : 1;
                    while (1)
                    {
                        tx++, ty += dir;
                        if (tx < 1 || ty < 1 || tx > n || ty > n || b[tx][ty]) break;
                        id[i][tx][ty] = p;
                    }
                }
            }
    g.resize(p + 1);
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= n; y++)
            if (!b[x][y])
                g[id[0][x][y]].push_back(id[1][x][y]);

    match = vector<int>(p + 1, -1);
    for (int i = 1; i <= p; i++)
    {
        visited = vector<bool>(p + 1, false);
        if (mbm(i)) ans++;
    }
    cout << ans;
}

비숍2 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글