[DFS] 1799번 비숍

1799번 비숍

 

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

 

문제

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

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

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

 

입력

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

 

출력

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

 

예제 입력

5
1 1 0 1 1
0 1 0 0 0
1 0 1 0 1
1 0 0 0 0
1 0 1 1 1

 

예제 출력

7

 

해결방법

⭐️ 1차 시도 ⭐️

시간 초과

 

처음에는 N-Queen 과 같은 방식으로 접근했다

솔루션은 다음과 같다

• 1) 비숍을 놓을 수 있는 곳을 기준으로 DFS + 백트래킹 수행
• 2) 그 과정에서, 양쪽 위 대각선을 확인하여 비숍을 두고 최대값 갱신

 

10하지만 ⏰시간 초과가 발생했다...

만약 모든 체스판이 1이라고 가정하면, 2^(10*10) 의 시간이 발생한다

따라서 당연히! 시간 초과가 발생한다

 

만약 모든 체스판이 1인 경우 많은 시간을 요구하게 된다

 

⭐️ 2차 시도 ⭐️

맞았습니다!

마이구미 님의 블로그

 

시간복잡도를 줄이기 위해서는 체스판의 특징을 생각해봐야한다

체스판을 흑∙백 으로 구분한다면??

1차 시도 때의 2^(10*10) 을 2^(5*5) + 2^(5*5) 로 바꿀 수 있을 것이다!!

 

시간 복잡도

• 변경 전 : O(2^(n*n))

• 변경 후 : O(2^(n/2*n/2) + 2^(n/2\*n/2))

 

 

[Black Area]

void dfs_b(int ind,int cnt){
    // 최대 비숍의 개수 갱신
    ans_b = max(ans_b,cnt);
    
    // DFS 탐색
    for(int i=ind; i<possible_area.size(); i++){
        int x = possible_area[i].first;
        int y = possible_area[i].second;
        
        // '짝수 행'인 경우 → 열의 인덱스 짝수
        if(x%2 == 0 && y%2 != 0) continue;
        // '홀수 행'인 경우 → 열의 인덱스 홀수
        else if(x%2 == 1 && y%2 != 1) continue;
        
        if(!bishop[x][y] && is_possible(x,y)){
            bishop[x][y] = true;
            dfs_b(i+1,cnt+1);
            bishop[x][y] = false;
        }
    }
}

[White Area]

void dfs_w(int ind,int cnt){
    // 최대 비숍의 개수 갱신
    ans_w = max(ans_w,cnt);
    
    // DFS 탐색
    for(int i=ind; i<possible_area.size(); i++){
        int x = possible_area[i].first;
        int y = possible_area[i].second;
        
        // '짝수 행'인 경우 → 열의 인덱스 홀수
        if(x%2 == 0 && y%2 != 1) continue;
        // '홀수 행'인 경우 → 열의 인덱스 짝수
        else if(x%2 == 1 && y%2 != 0) continue;
        
        if(!bishop[x][y] && is_possible(x,y)){
            bishop[x][y] = true;
            dfs_w(i+1,cnt+1);
            bishop[x][y] = false;
        }
    }
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 11
#define INF 987654321
using namespace std;
typedef pair<int,int> node;

int n,ans_b,ans_w;
int map[MAX][MAX];
bool bishop[MAX][MAX];

vector<node> possible_area;

bool is_possible(int x,int y){
    // 왼쪽 위 대각선
    int nx = x - 1;
    int ny = y - 1;
    while(nx>=0 && ny>=0){
        if(bishop[nx][ny]) return false;
        nx--; ny--;
    }
    
    // 오른쪽 위 대각선
    nx = x - 1;
    ny = y + 1;
    while(nx>=0 && ny<n){
        if(bishop[nx][ny]) return false;
        nx--; ny++;
    }
    
    return true;
}

void dfs_b(int ind,int cnt){
    // 최대 비숍의 개수 갱신
    ans_b = max(ans_b,cnt);
    
    // DFS 탐색
    for(int i=ind; i<possible_area.size(); i++){
        int x = possible_area[i].first;
        int y = possible_area[i].second;
        
        // '짝수 행'인 경우 → 열의 인덱스 짝수
        if(x%2 == 0 && y%2 != 0) continue;
        // '홀수 행'인 경우 → 열의 인덱스 홀수
        else if(x%2 == 1 && y%2 != 1) continue;
        
        if(!bishop[x][y] && is_possible(x,y)){
            bishop[x][y] = true;
            dfs_b(i+1,cnt+1);
            bishop[x][y] = false;
        }
    }
}

void dfs_w(int ind,int cnt){
    // 최대 비숍의 개수 갱신
    ans_w = max(ans_w,cnt);
    
    // DFS 탐색
    for(int i=ind; i<possible_area.size(); i++){
        int x = possible_area[i].first;
        int y = possible_area[i].second;
        
        // '짝수 행'인 경우 → 열의 인덱스 홀수
        if(x%2 == 0 && y%2 != 1) continue;
        // '홀수 행'인 경우 → 열의 인덱스 짝수
        else if(x%2 == 1 && y%2 != 0) continue;
        
        if(!bishop[x][y] && is_possible(x,y)){
            bishop[x][y] = true;
            dfs_w(i+1,cnt+1);
            bishop[x][y] = false;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
            
            if(map[i][j] == 1) possible_area.push_back(node(i,j));
        }
    }
    
    memset(bishop, false, sizeof(bishop));
    
    ans_b = ans_w = 0;
    dfs_b(0,0);
    dfs_w(0,0);
    cout << ans_b + ans_w << "\n";
}