비숍

 

백준 온라인저지의 비숍문제다.

 

예전에 풀어본 경험이 있는 N-Queen문제와 비슷한문제 였고, NQueen 풀떄보다 훨씬 더 많이 시간을잡아먹었고 많이틀렸다.

 

다른것보다, 이런 2차원 배열에서 대각선으로 주는 조건은 행 + 열 , 행 - 열 이런식으로해서 규칙성을 찾아낼수가 있어서,  r[21] c[21] 배열에, 해당하는 규칙에서 맞는것들을 체킹해주면서 진행하는 재귀함수를 한큐에 썼는데

이게 시간복잡도가 생각보다 엄청나게 큰모양이다. 사실상 전부 해보는거니까 O(N*N)의 시간복잡도가 소요될거라 예상한다.

 

그래서 일단 비숍이 들어갈수 있는 후보인 맵의 1을 벡터 페어로 잡아서 해봤는데,

#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>

using namespace std;

int n;
int map[11][11];
bool r[21];
bool c[21];

vector<pair<int,int>> v;

int ans = 0;

void go(int i, int cnt){
    if(i == v.size())
    {
        if( cnt > ans ) ans = cnt;
        return;
    }
    go(i+1, cnt);
    if(r[v[i].first+v[i].second] == false && c[10+v[i].first-v[i].second] == false && map[v[i].first][v[i].second] == 1) {
        map[v[i].first][v[i].second] = 2;
        r[v[i].first + v[i].second] = true;
        c[10 + v[i].first - v[i].second] = true;
        go(i + 1, cnt + 1);
        map[v[i].first][v[i].second] = 1;
        r[v[i].first + v[i].second] = false;
        c[10 + v[i].first - v[i].second] = false;
    }



}


int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d", &map[i][j]);
            if(map[i][j] == 1){
                v.push_back({i,j});
            }
        }
    }

    go(0, 0);

    cout<<ans<<endl;

}

역시나 시간복잡도가 터져버린다. 이건정말해도해도 적응이안되는부분...

정말 여러번 시도해보고했지만, 다른 조건이 생각이안나서

두개를 나눴고 전부다해보는방식을 했는데, 여기서 코드를 짜기전에 규칙을 먼저 생각해보면

체스판에서 비숍은 흰 검, 흰, 검 되있는 맵에서 본인이 위치하고있는 색상의 맵만 이동할수있다는점이다.

따라서 , 다른 색상의 위치에서 존재하는 비숍들은 그 다른위치에서 존재할 비숍들의 영향을 주지않고, 이는 충분히

독립적이라고 할수있다. 따라서 시간복잡도는(N/2 *N/2) 정도가될것이라 예상한다.

 

#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>

using namespace std;

int n;
int map[11][11];
int r[21];
int c[21];


int ans = 0;

void go(int i,int j, int cnt){
    if( cnt > ans ) ans = cnt;


    if(j >= n) {
        i++;
        if (i % 2 == 0)
            j = 0;
        else j = 1;
    }
    if(i >= n) return;

    if (r[i + j] == 0 && map[i][j] == 1&& c[10 + i - j] == 0 ) {
            r[i + j] = 1;
            c[10 + i - j] = 1;
            go(i, j + 2, cnt + 1);
            r[i + j] = 0;
            c[10 + i - j] = 0;

    }
    go(i,j+2, cnt);
}
void go1(int i,int j, int cnt){
    if( cnt > ans ) ans = cnt;


    if(j >= n) {
        i++;
        if (i % 2 == 0)
            j = 1;
        else j = 0;
    }
    if(i >= n) return;

    if (r[i + j] == 0 && map[i][j] == 1&& c[10 + i - j] == 0 ) {
        r[i + j] = 1;
        c[10 + i - j] = 1;
        go1(i, j + 2, cnt + 1);
        r[i + j] = 0;
        c[10 + i - j] = 0;

    }
    go1(i,j+2, cnt);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%d", &map[i][j]);
        }
    }
    int sum = 0;
    go(0,0, 0);
    sum = ans;
    ans = 0;

    go1(0,1,0);
    sum+=ans;
    cout<<sum<<endl;
    return 0;
}

 이런식으로 , 검정색, 흰색일때 구간을나눠서 재귀함수를 돌려봤다.

시간은 역시 초과하지않았고 정확하게 잘나왔다.