[1574번] 룩 어택

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

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

이 문제를 풀기전에 반드시 

[1760번] N-Rook :: http://www.crocus.co.kr/765 문제를 풀기를 바란다.

위의 링크를 따라가면 룩에 대해 자세하게 설명을 해두었기에 이 문제의 설명은 하지 않고, N-Rook과의 차이만 말하도록 한다.

N-Rook은 벽이 존재하여 이 문제보다 더 어려운 문제이다.

하지만, 저 문제를 해결하게 되면 이 문제는 하위 호환 문제이기에 가져갈 수 있는 문제가 된다.

N-Rook에서는 범위가 15000이 되곤 했지만, 여기서는 벽이 존재하지 않기에 넘버링이 MAX_N내에 끝이난다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <vector>
#include <algorithm>
 
#define MAX_N 302
using namespace std;
 
int map[MAX_N][MAX_N];
int col[MAX_N][MAX_N];
int row[MAX_N][MAX_N];
 
vector<int> adj[MAX_N];
vector<int> aMatch;
vector<int> bMatch;
int visit[MAX_N];
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()
{
    int k;
    scanf("%d %d %d", &n, &m, &k);
 
    for (int i = 1; i <= k; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        map[a][b] = 1;
    }
    
    int cnt = 1;
 
    // 행 기준으로 넘버링
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            col[i][j] = cnt;
        cnt++;            
    }
 
    // 열 기준으로 넘버링
    cnt = 1;
    for (int j = 1; j <= m; j++)
    {
        for (int i = 1; i <= n; i++)
            row[i][j] = cnt;
        cnt++;
    }
 
    int maxR = 0, maxC = 0;
 
    // 1인 곳은 이분 그래프에 포함되지 않도록 한다.
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; 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 >>