1799 비숍

문제 링크

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

int n, x, b[21];
vector<int> adj[21];
bool vis[21];

void input() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            scanf("%d", &x);
            if (x) adj[n - i + j].push_back(i + j + 1); //놓을 있는 자리인 경우 adj[좌상우하 대각선 번호].pushback(우상좌하 대각선 번호)
        }
    n <<= 1; // n *= 2
}

bool matching(int cur) {
    if (vis[cur]) return false;
    vis[cur] = true;
    for (int next : adj[cur]) {
        if (b[next] == -1 || matching(b[next])) {
            b[next] = cur;
            return true;
        }
    }
    return false;
}

int proc() {
    int match = 0;
    for (int i = 1; i < n; i++) {
        memset(vis, 0, sizeof(vis));
        if (matching(i)) match++;
    }
    return match;
}

int main() {
    memset(b, -1, sizeof(b));
    input();
    printf("%d", proc());
    return 0;
}

1. 최대값 이상을 탐색하려고 하면 나온다. 남은 비숍을 전부 추가해도 최대값이하인 경우 나온다.
2. 흰색 바닥과과 검은 바닥 2개로 나누어 계산하면 시간이 많이 줄어든다.
3. 위의 소스코드 방법 (0ms)

<N - Queen 참고코드>

#include <bits/stdc++.h>
using namespace std;

int cnt = 0;
int n;
int place[20]; // 퀸은 (i, place[i])에 위치한다.
void func(int cur) { // cur번째 row에 말을 배치할 예정임
    if (cur == n) { // N개를 놓는데 성공했다면
        cnt++;
        return;
    }
    for (int i = 0; i < n; i++) { // (cur, i)에 퀸을 놓을 예정
        bool isvalid = true; // (cur, i)에 놓아도 되는지
        for (int j = 0; j < cur; j++) {
            if (place[j] == i or cur + i == j + place[j] or cur - i == j - place[j]) { // 열, 대각선에 퀸이 있는지 체크
                isvalid = false;
                break;
            }
        }
        if (isvalid) {
            place[cur] = i;
            func(cur + 1);
        }
    }
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    func(0);
    cout << cnt;
}