[9525번] 룩 배치하기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

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

이분 매칭 룩 시리즈의 코드가 돌고 도는 것 같다.

요구사항만 다를 뿐, 결국 코드적인 측면에서는 똑같이 해결하면 되는 문제들이 계속 나오고 있다.

룩 시리즈 문제를 꼭 풀어보고 이 문제를 풀어보거나, 이 문제를 풀어보고 꼭 룩 시리즈를 함께 가져가길 바란다.

룩 시리즈 문제 :: http://www.crocus.co.kr/search/rook

[1760번] N-Rook :: http://www.crocus.co.kr/765 이 문제의 내용을 이용하면 쉽게 해결 할 수 있는 룩 배치하기 문제이다.

코드가 동일하므로 여기서 설명은 생략하도록 한다.

(저기서 2라는 표현이 여기서 X라는 표현과 같고, 여기는 0과 2만 존재, 저 문제에서는 0, 1, 2가 존재한다.)

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <vector>
#include <algorithm>
 
#define MAX_N 102
using namespace std;
 
bool map[MAX_N][MAX_N];
int col[MAX_N][MAX_N];
int row[MAX_N][MAX_N];
 
vector<int> adj[5002];
vector<int> aMatch;
vector<int> bMatch;
int visit[5002];
int visitCnt;
 
int n, m;
 
bool dfs(int a)
{
    if (visit[a] == visitCnt)
        return false;
 
    visit[a] = visitCnt;
 
    for (int next = 0; next < adj[a].size(); next++)
    {
        int b = adj[a][next];
 
        if (bMatch[b] == -1 || dfs(bMatch[b]))
        {
            aMatch[a] = b;
            bMatch[b] = a;
 
            return true;
        }
    }
 
    return false;
}
 
int bipartiteMatch()
{
    aMatch = vector<int>(n + 1, -1);
    bMatch = vector<int>(m + 1, -1);
 
    int ans = 0;
 
    for (int a = 1; a <= n; a++)
    {
        visitCnt++;
        ans += dfs(a);
    }
 
    return ans;
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        getchar();
        for (int j = 1; j <= n; j++)
        {
            char ch;
            scanf("%c", &ch);
            if (ch == 'X')
                map[i][j] = 1;
        }
    }
    int cnt = 1;
 
    // 행 기준으로 넘버링
    bool chk;
    for (int i = 1; i <= n; i++)
    {
        chk = false;
 
        for (int j = 1; j <= n; j++)
        {
            if (map[i][j] == 0)
            {
                col[i][j] = cnt;
                chk = true;
            }
 
            else
                if (chk)
                {
                    cnt++;
                    chk = false;
                }
        }
 
        if (chk)
            cnt++;
 
    }
 
    // 열 기준으로 넘버링
    cnt = 1;
    for (int j = 1; j <= n; j++)
    {
        chk = false;
 
        for (int i = 1; i <= n; i++)
        {
            if (map[i][j] == 0)
            {
                row[i][j] = cnt;
                chk = true;
            }
 
            else
                if (chk)
                {
                    cnt++;
                    chk = false;
                }
        }
 
        if (chk)
            cnt++;
    }
 
    int maxR = 0, maxC = 0;
 
    // 1인 곳은 이분 그래프에 포함되지 않도록 한다.
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (map[i][j] == 0)
            {
                adj[row[i][j]].push_back(col[i][j]);
 
                maxR = max(maxR, row[i][j]);
                maxC = max(maxC, col[i][j]);
            }
 
    // 이제는 n,m으로 보는 것이 아닌 넘버링 단위로 봐야한다.
    n = maxR;
    m = maxC;
 
    int get = bipartiteMatch();
 
    printf("%d", get);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>