1799. 비숍

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

1799번: 비숍

 

풀이

필요 알고리즘: 백트래킹

 

일단 이 문제를 백트래킹으로 풀 때 시간 복잡도를 생각해 보자. 각 칸은 비숍을 놓는 것이 가능/불가능 두 경우로 나뉘어지고, 이 칸이 최대 10 × 10 = 100칸 존재하니 가능한 모든 경우를 최대 2¹⁰⁰번 확인하게 된다. 연산 횟수가 무지막지하게 크므로 시간 초과가 걱정되는데, 실제로 필자가 이렇게 풀다 시간 초과가 나 버렸다. 그렇다면 이걸 조금이라도 줄일 수 있는 방법이 있을까?

 

방법은 비숍의 특성을 이용하는 것이다. 비숍은 대각선으로만 이동할 수 있으므로, 흰색 칸의 비숍은 흰색만, 검은색 칸의 비숍은 검은색 칸만 돌아다닐 수 있다. 즉, 흰 칸과 검은 칸 각각에서 비숍의 위치가 서로를 간섭하지 않으므로 각각을 분리하여 경우의 수를 따질 수 있다. 그러면 흰 칸과 검은 칸은 각각 최대 50칸이므로, 최대 2⁵⁰ × 2⁵⁰ = 2⁵¹번 확인하게 된다. 아까의 연산 횟수의 제곱근 수준으로 크게 줄어든 것을 확인할 수 있다.

 

그러면 이를 바탕으로 코드를 작성해 보자. 비숍이 서로를 잡을 수 없는 위치에 놓을 수 있는지는 다음과 같이 추상화하여 확인할 수 있다.

두 배열 check1, check2를 선언한다. 각 배열은 대각선에 비숍이 놓여졌는지 정보를 저장하는데, check1은 우상단-좌하단 대각선을, check2는 좌상단-우하단 대각선을 저장한다. 이렇게 하면 비숍이 이미 놓여져 있으면 그 칸은 피하고, 없으면 비숍을 놓도록 경우를 짤 수 있다.

 

시간 복잡도

체스판의 한 변의 길이를 \(n\)이라고 하면, 흰 칸과 검은 칸은 각각 \(\frac{n}{2}\)개이다(\(n\)이 홀수이면 흰 칸이 하나 더 많으나, 무시해도 무방). 이 두 가지 색의 칸에서 각각 비숍 배치 가능/불가능 2가지 경우를 따지므로, 시간 복잡도는 \(O(2^{\frac{n}{2}} × 2^{\frac{n}{2}}) = O(2 ^{\frac{n}{2}+1})\)이다.

 

소스코드

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int n;
int board[10][10];
vector<pair<int, int>> bishopEven;
vector<pair<int, int>> bishopOdd;
bool check1[19], check2[19];
int ans, res, tmp;

void backtrack(vector<pair<int, int>>& bishop, int id) {
    if(id >= bishop.size()) return;
    
    for(int i = id; i < bishop.size(); i++) {
        int URtoDL = bishop[i].first + bishop[i].second;
        int ULtoDR = n + bishop[i].first - bishop[i].second - 1;
        if(!check1[URtoDL] && !check2[ULtoDR]) {
            check1[URtoDL] = true;
            check2[ULtoDR] = true;
            res = max(res, ++tmp);
            
            backtrack(bishop, i + 1);
            check1[URtoDL] = false;
            check2[ULtoDR] = false;
            tmp--;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> board[i][j];
            if(board[i][j] && (i + j) % 2 == 0)
                bishopEven.emplace_back(i, j);
            if(board[i][j] && (i + j) % 2 == 1)
                bishopOdd.emplace_back(i, j);
        }
    }
    
    backtrack(bishopEven, 0);
    ans += res; res = 0;
    backtrack(bishopOdd, 0);
    ans += res;
    cout << ans;
    return 0;
}

실행 시간: 20 ms

사용 메모리: 2020 KB

 

필자는 먼저 비숍을 놓을 수 있는 칸을 별도의 배열에 저장하고, 그 배열을 대상으로 백트래킹을 시행하였다. 다른 풀이에서는 체스판을 대상으로 백트래킹을 하며 비숍을 놓을 수 있는 칸인지 여부를 한꺼번에 확인했는데, 필자의 확인 결과 어느 쪽이든 실행 속도엔 큰 차이가 없었다.