[그래프] BISHOPS 비숍

1. 문제

 

게임판과 장애물의 위치가 주어진다.

 

이 게임판 위에서 비숍을 서로 죽일수 없도록

 

최대한 몇개 배열할 수 있는지 계산하는 문제이다.

 

 

2. 이분 매칭

 

비숍은 대각선으로만 이동할 수 있다.

 

오른쪽으로 가는 대각선과 왼쪽으로 가는 대각선 두개로

 

비숍의 위치를 나타낼 수 있다.

 

그러므로 해당 대각선에 비숍이 두개 있을 경우 서로 죽일 수 있다.

 

이를 이용하여 

 

오른쪽 대각선과 왼쪽대각선을 a그룹 b그룹으로 나누어 이분 할 수 있으며

 

최대한 많이 비숍을 배열해야하므로 이는 이분 최대 매칭 문제가 된다.

 

따라서 그래프만 적절히 표현하면 문제는 쉽게 해결된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <iomanip>
 
using namespace std;
int N;
vector<vector<int> > gameBoard;
vector<vector<bool> > adj;
vector<vector<pair<int, int> > > mem;
vector<vector<int> > groupA;
vector<vector<int> > groupB;
vector<bool> visited;
vector<int> matchA, matchB;
 
int an, bn;
 
bool dfs(int a)
{
    if(visited[a]) return false;
    visited[a] = true;
    for(int b = 0; b < bn; b++)
    {
        if(adj[a][b])
            if(matchB[b] == -1 || dfs(matchB[b]))
            {
                matchA[a] = b;
                matchB[b] = a;
                return true;
            }
    }
 
    return false;
}
 
int solve()
{
    int ret = 0;
    matchA = vector<int>(an, -1);
    matchB = vector<int>(bn, -1);
    for(int i = 0; i < an; i++)
    {
        visited = vector<bool>(an, false);
        if(dfs(i))
            ret++;
    }
    return ret;
}
 
int main()
{
    int C;
    cin>>C;
    while(C--)
    {
        cin>>N;
        gameBoard = vector<vector<int> > (N+2, vector<int>(N+2));
        groupA = vector<vector<int> > (N+2, vector<int>(N+2, -1));
        groupB = vector<vector<int> > (N+2, vector<int>(N+2, -1));
        an = bn = 0;
        getchar();
        for(int i = 1; i < N+1; i++)
            for(int j = 1; j < N+1; j++)
            {
                char ch;
                cin>>ch;
                gameBoard[i][j] = (int)ch;
            }
        for(int i = 0; i < N+2; i++)
        {
            gameBoard[0][i] = gameBoard[N+1][i] = (int)'*';
            gameBoard[i][0] = gameBoard[i][N+1] = (int)'*';
        }
 
        for(int i = 1; i < N + 1; i++)
            for(int j = 1; j < N + 1; j++)
            {
                if(gameBoard[i][j] == '*') 
                {
                    groupA[i][j] = groupB[i][j] = -1;
                    continue;
                }
                if(gameBoard[i-1][j-1] == '*')
                    groupA[i][j] = an++;
                else
                    groupA[i][j] = groupA[i-1][j-1];
 
                if(gameBoard[i-1][j+1] == '*')
                    groupB[i][j] = bn++;
                else   
                    groupB[i][j] = groupB[i-1][j+1];
            }
        adj = vector<vector<bool> > (an, vector<bool>(bn, false));
 
        for(int i = 1; i < N + 1; i++)
            for(int j = 1; j < N + 1; j++)
                if(groupA[i][j] != -1 && groupB[i][j] != -1)
                    adj[groupA[i][j]][groupB[i][j]] = true;
 
        cout<<solve()<<"\n";
    }
}

• BISHOPS

algospot.com :: BISHOPS