[백준/BOJ] 1799번 비숍 (C++)

www.acmicpc.net/problem/1799

1799번: 비숍

난이도 높은 DFS + 백트래킹 문제

처음에 N-Queen 문제처럼 접근했는데 시간초과가 발생했습니다. 시간초과가 발생하는 이유는 입력받은 값이 전부 1일 때 최악의 경우 2^10*10의 시간복잡도를 가질 수 있기 때문이라고 합니다. 따라서 이 문제를 해결하기 위해서는 체스판의 검은 칸, 흰칸을 나누어 DFS를 진행하는 것입니다. 그러면 시간 복잡도가 2^5*5+2^5*5로 확연히 줄어듭니다. 이러한 접근법을 생각해내는게 상당히 어려운 것 같습니다.

 

#include <iostream>
#include <vector>
#define MAX 11
using namespace std;

int map[MAX][MAX];
bool visit[MAX][MAX];
vector<pair<int, int> > v;
int n, blackAns, whiteAns;

// 비숍을 둘 수 있는지 확인
bool isPossible(int x, int y) {
    // 왼쪽 위 대각선 이동
    int nx = x - 1;
    int ny = y - 1;
    while(nx >= 0 && ny >= 0) {
        // 이미 비숍을 둔 곳이라면 false를 리턴
        if(visit[nx][ny]) return false;
        nx--;
        ny--;
    }
    
    // 오른쪽 위 대각선 이동
    nx = x - 1;
    ny = y + 1;
    while(nx >= 0 && ny < n) {
        // 이미 비숍을 둔 곳이라면 false를 리턴
        if(visit[nx][ny]) return false;
        nx--;
        ny++;
    }
    
    // 각 대각선을 체크했을 때 비숍이 없었다면 true를 리턴
    return true;
}

// 검은 칸 탐색 DFS
void blackDFS(int idx, int cnt) {
    // 검은 칸에 둘 수 있는 비숍의 최대값
    blackAns = max(blackAns, cnt);
    
    for(int i = idx; i < v.size(); i++) {
        int x = v[i].first;
        int y = v[i].second;
        // 짝수행에 홀수열은 흰 칸이므로
        if(x % 2 == 0 && y % 2 == 1) continue;
        // 홀수행에 짝수열은 흰 칸이므로
        if(x % 2 == 1 && y % 2 == 0) continue;
        if(!visit[x][y] && isPossible(x, y)) {
            visit[x][y] = true;
            blackDFS(i + 1, cnt + 1);
            visit[x][y] = false;
        }
    }
}

// 흰 칸 탐색 DFS
void whiteDFS(int idx, int cnt) {
    // 흰 칸에 둘 수 있는 비숍의 최대값
    whiteAns = max(whiteAns, cnt);
    
    for(int i = idx; i < v.size(); i++) {
        int x = v[i].first;
        int y = v[i].second;
        // 짝수행에 짝수열은 검은 칸이므로
        if(x % 2 == 0 && y % 2 == 0) continue;
        // 홀수행에 홀수열은 검은 칸이므로
        if(x % 2 == 1 && y % 2 == 1) continue;
        if(!visit[x][y] && isPossible(x, y)) {
            visit[x][y] = true;
            whiteDFS(i + 1, cnt + 1);
            visit[x][y] = false;
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    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) v.push_back({i, j});
        }
    }
    
    blackDFS(0, 0);
    whiteDFS(0, 0);
    
    cout<<blackAns + whiteAns;
}