1574 룩 어택

r*c 크기의 체스판이 있고 n개의 룩을 놓을 수 없는 칸(룩들이 빈칸을 사이에 두고 배치되었을 때 공격 조건을 만족하면 공격 가능하다. 즉 공격 가능 여부에는 영향을 미치지 않는다.)이 있을 때 최대 룩을 몇 개 놓을 수 있는지 출력하는 문제다.

  1. n개의 룩을 받으면서 동시에 map에 -1로 기록을 해놓는다.

  2. map[i][j]가 -1이 아니면 i->j로 간선을 연결한다.(1번방법)

  3. 이분매칭

※ 맵을 만들어놓기 싫다면 1<=i<=r, 1<=j<=c 모든 간선을 연결 해 놓고 빈칸의 좌표를 입력받으며 해당 간선을 지워도 된다(2번방법). 속도는 동일하지만 메모리는 범위가 300까지밖에 안되기 때문에 2번 방법이 훨씬 적게든다.

<1번방법 코드>

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
 
int r, c, n, x, y, map[301][301];
vector<int> v[301];
vector<int> p(301, -1);
vector<bool> ch(301);
 
int dfs(int x) {
    if (x == -1) return 1;
    for (auto i : v[x]) {
        if (ch[i]) continue;
        ch[i] = 1;
        if (dfs(p[i])) {
            p[i] = x;
            return 1;
        }
    }
    return 0;
}
 
int main() {
    scanf("%d%d%d", &r, &c, &n);
    while (n--) {
        scanf("%d%d", &x, &y);
        map[x][y] = -1;
    }
    for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++)
        if (!map[i][j]) v[i].push_back(j);
    int ans = 0;
    for (int i = 1; i <= r; i++) if (v[i].size()) {
        fill(ch.begin(), ch.end(), false);
        ans += dfs(i);
    }
    printf("%d\n", ans);
    return 0;
}

<2번방법 코드>

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
 
int r, c, n, x, y, v[301][301], p[301];
bool ch[301];
 
int dfs(int x) {
    if (x == -1) return 1;
    for (int i = 1; i <= c; i++) {
        if (ch[i] || !v[x][i]) continue;
        ch[i] = 1;
        if (dfs(p[i])) {
            p[i] = x;
            return 1;
        }
    }
    return 0;
}
 
int main() {
    memset(p, -1, sizeof(p));
    scanf("%d%d%d", &r, &c, &n);
    for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++) v[i][j] = 1;
    while (n--) {
        scanf("%d%d", &x, &y);
        v[x][y] = 0;
    }
    int ans = 0;
    for (int i = 1; i <= r; i++) {
        memset(ch, false, sizeof(ch));
        ans += dfs(i);
    }
    printf("%d\n", ans);
    return 0;
}