비숍

백준 1799번: 비숍

아이디어

비숍을 하나 놓으면 그 비숍을 기준으로 기울기가 1, -1인 대각선 방향 모두 비숍을 놓을 수 없다. 기울기가 1인 대각선 방향 좌표의 합(row + col)이 모두 일정하고, 기울기가 -1인 대각선 방향 좌표의 차(row-col)도 모두 일정하다. 이를 통해 비숍을 놓을지 말지 결정할 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, MCNT = 0, ANS = 0;
bool rmc[20]; // rmc[k]: -k, rmc[k+N]: k
bool rpc[20];
int arr[10][10];
vector<pair<int, int>> vo;
vector<pair<int, int>> ve;


void solve(vector<pair<int, int>>::iterator iter, int cnt) {
    if (iter == vo.end() || iter == ve.end()) {
        MCNT = max(MCNT, cnt);
        return;
    }
    
    int row = (*iter).first;
    int col = (*iter).second;
    
    if (!rmc[row-col+N] && !rpc[row+col]) {
        rmc[row-col+N] = true;
        rpc[row+col] = true;
        solve(iter+1, cnt+1);
        rmc[row-col+N] = false;
        rpc[row+col] = false;
    }
    solve(iter+1, cnt);
    
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                if ((i+j)%2) {
                    vo.push_back({i, j});
                }
                else {
                    ve.push_back({i, j});
                }
            }
        }
    }
    
    auto iter = vo.begin();
    solve(iter, 0);
    ANS = MCNT;
    MCNT = 0;
    iter = ve.begin();
    solve(iter, 0);
    ANS += MCNT;
    cout << ANS;
    
    return 0;
}

여담

그냥 모든 경우의 수를 탐색하면 시간초과다. O(2^(N*N))의 시간복잡도를 가지고 2^100이면 죽을때까지 컴퓨터를 켜놔도 풀리지 않을 것이다.

체스판에서 백색 칸의 비숍과 흑색 칸의 비숍은 서로 만날 수 없다. 인덱스의 합이 홀수인 경우, 짝수인 경우로 나눠서 풀면 O(2^((N/2)*(N/2)))의 시간복잡도를 가지고 2^25이면 충분히 풀 수 있다.