[백준-1799] 비숍

시간 복잡도가 중요한 문제이다. 일단 제한 시간을 보면 10초인 것을 볼 수 있다.

허나 입력값이 100개인 배열에서 일일이 다 비숍을 넣어가면서 백트래킹을 하게 된다면 O(2^(10*10)) 이 되어 터져버리게 된다.

이를 위해 체스판의 특징을 생각해 흑,백 으로 나눠 로직을 짜보려고 한다. 이렇게 되면 복잡도가 O(2^(5*5)) 가 되어 문제 없이 제한시간을 맞추게 된다. 분할해서 생각한다면 로직은 일반 백트래킹과 다를바 없어 넘어가도록 하겠다.

다만 흑,백으로 나누어 check 배열을 두고 확인하는 로직만 유심히 보면 될것 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int N;
int chess[11][11];
int color[11][11];
int check[11][11];
int dx[] = { -1,1,1,-1 };
int dy[] = { 1,-1,1,-1 };
int max_cnt[2]; 
vector<vector<pii>> zero(2);

bool check_bis(int cx, int cy) {
    for (int i = 0; i < 4; i++) {
        int nx = cx + dx[i];
        int ny = cy + dy[i];

        for (int j = 1; j < N; j++) {
            if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
            if (check[nx][ny]) return false;

            nx += dx[i];
            ny += dy[i];
        }
    }
    return true;
}

void dfs(int n, int cnt, int col) {
    max_cnt[col] = max(cnt, max_cnt[col]);
    if (n + 1 >= zero[col].size()) 
        return;
    
    for (int i = n + 1; i < zero[col].size(); i++) {
        int cx = zero[col][i].first;
        int cy = zero[col][i].second;
        if (color[cx][cy] != col) continue;
        if (check[cx][cy] == 1) continue;
        if (!check_bis(cx, cy)) continue;
        if (chess[cx][cy] == 0) continue;

        check[cx][cy] = 1;
        dfs(i, cnt + 1, col);
        check[cx][cy] = 0;
    }
}

int main() {
    cin >> N;
    int input;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> chess[i][j];
            if ((i + j) % 2 == 0) { 
            // 백색 : 1, 흑색 : 0
                color[i][j] = 0;
                if(chess[i][j]) zero[0].push_back({ i,j });
            }
            else if ((i + j) % 2 == 1) {
                color[i][j] = 1;
                if (chess[i][j]) zero[1].push_back({ i,j });
            }
        }
    }

    dfs(-1, 0, 0);
    dfs(-1, 0, 1);
    
    printf("%d", max_cnt[0] + max_cnt[1]);
    return 0;
}

 

 

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

1799번: 비숍