[백준] 1799번 비숍 c++

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

1799번: 비숍

 

문제

서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.

< 그림 1 >

그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다.  색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.

< 그림 2 >

< 그림 3 >

정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.

출력

첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.

 

 

접근방법 및 풀이

- 백트레킹으로 해결하였다.

처음에는 단순히 모든 경우를 고려하는 방법으로 코드를 짰다가 시간이 10초임에도 불구하고 시간초과가 났다.

생각을 거듭해도 진전이 보이지 않아 구글링을 하여 힌트를 얻었다.

보드판의 흰칸과 검은칸은 서로 영향을 받지 않으므로 두가지 경우로 나누어 탐색을 진행하면 복잡도가 2^(N*N)에서 2^(n/2 * n/2)로 줄어든다는 것을 알게되었다.

비숍의 이동특성 상 흰/검은 칸이 독립적인 것이라는을 생각해 내기가 어려웠다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n;
int b[11][10];
int v[11][10]={0};
int result=0;
int r[2]={0};

int dx[4]={1,1,-1,-1};
int dy[4]={-1,1,1,-1};

//-1 비숍
//0 빈자리
//1 못놓는자리

bool check(int x, int y, int res[][10]){
    for(int i=1; i<n; i++){
        for(int j=0; j<4; j++){
            int nx = x + dx[j]*i;
            int ny = y + dy[j]*i;
            if(nx>=0 && ny>=0 && nx < n && ny < n){
                if(res[nx][ny]==-1){
                    return false;
                }
            }
        }
    }
    return true;
}

void bt(int x, int y, int res[][10], int c, int k, vector<pair<int, int>> a){
    if(x==n){
        r[k] = max(r[k], c);
        return ;
    }
    if(y==n-1) bt(x+1,0,res,c,k,a);
    else bt(x,y+1,res,c,k,a);
    
    
    if(res[x][y]==0) return ;//디버깅 : 얘가 맨 위에 있으면 비숍 놓지않고 탐색하는 경우가 막히게 된다.
    if(v[x][y]==k) return ;
    
    if(check(x,y,res)){
        res[x][y]=-1;
        a.push_back({x,y});
        if(y==n-1) bt(x+1,0,res,c+1,k,a);
        else bt(x,y+1,res,c+1,k,a);
        res[x][y]=1;
        a.pop_back();
    }
    return ;
}

int main()
{
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &b[i][j]);
            if((i+j)%2==0) v[i][j]=1;
        }
    }
    vector<pair<int, int>> a;
    bt(0,0,b,0,0, a);
    bt(0,0,b,0,1,a);
    cout << r[0]+r[1];
    return 0;
}

 

느낀점

끈질기게 반례를 찾아서 결국 무엇이 문제인지 파악하고 해결했다. 너무 뿌듯하고 덕분에 자신감이 생겼다. 항상 중간에 걸리는 케이스가 있어서 틀리게 되면 반례를 직접 만들생각은 안하고 찾아다니기만 하는 나 자신이었는데 이제는 스스로 반례를 만들어 끝까지 해결해야 겠다는 마인드가 생겼다.

 탐색 종료조건을 처음에 x,y == n-1,n-1로 해서 마지막칸이 비숍을 놓을 수 있는 경우에 비숍을 놓지못하고 종료되었다. 이를 해결하기 위해 배열 한줄을 더 여유롭게 [11][10]으로 해서 x==n일때 탐색을 종료하는 것으로 수정하였다.