Baekjoon 1799번 비숍

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int s;
vector<vector<int>> board(10, vector<int>(10, 0));
vector<pair<int, int>> white, black;

void change(int r, int c, int var){
    int R, C;
    // ↙
    R = r;
    C = c;
    while(R < s-1 && C > 0){
        R++;
        C--;
        if(board[R][C])
            board[R][C] += var;
    }
    // ↗
    R = r;
    C = c;
    while(R > 0 && C < s-1){
        R--;
        C++;
        if(board[R][C])
            board[R][C] += var;
    }
    // ↖
    R = r;
    C = c;
    while(R > 0 && C > 0){
        R--;
        C--;
        if(board[R][C])
            board[R][C] += var;
    }
    // ↘
    R = r;
    C = c;
    while(R < s-1 && C < s-1){
        R++;
        C++;
        if(board[R][C])
            board[R][C] += var;
    }
    // ·
    board[r][c] += var;
}

// backtracking
void solve(int idx, int cnt, int& bishop, vector<pair<int, int>>& put){
    for(int i = idx+1; i < put.size(); i++){
        int r = put[i].first;
        int c = put[i].second;
        if(board[r][c] == 1){
            change(r, c, 1);
            bishop = max(bishop, cnt+1);
            solve(i, cnt+1, bishop, put);
            change(r, c, -1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> s;
    for(int i = 0; i < s; i++){
        for(int j = 0; j < s; j++){
            cin >> board[i][j];
            if(board[i][j]){
                if((i+j)%2 == 0)
                    white.push_back(make_pair(i, j));
                else
                    black.push_back(make_pair(i, j));
            }
        }
    }
    int w, b;
    w = 0; b = 0;
    solve(-1, 0, w, white);
    solve(-1, 0, b, black);
    cout << w+b;
    return 0;
}

문제는 체스판 위 색칠된 부분에 비숍을 서로 잡을 수 없도록 가능한 많이 놓으려고 한다.

정답을 구하기 위해선 색칠된 칸마다 순서대로 비숍을 하나씩 놓아보는 방법이 있다. 구성이 동일하고 순서만 다른 경우는 같은 경우이기 때문에 조합의 수를 구해야 한다.

중복되지 않는 모든 경우의 수의 탐색은, 색칠된 칸의 좌표를 배열에 저장하고 현재 좌표 다음의 좌표들만 반복 호출한다. 보통 선택-미선택, 사용-미사용과 같은 조합의 경우를 따질 때 실행 과정을 손으로 따라가 보면 중복이 제거됨이 잘 보이지만, 이 문제는 직접 그려본 재귀 호출 과정만을 봐서는 알고리즘이 색칠된 모든 칸에 비숍을 둘 수 있는지 잘 확인하고 있는 걸까 의심이 든다.

그래서 호출되는 과정을 조금 더 자세히 풀어 나타내 보았다. 1부터 n-1개의 좌표가 각각 선택되는 경우, 선택되지 않는 경우로 모두 탐색이 진행되는 것을 눈으로 확인할 수 있었다.

위의 진행대로라면 좌표의 개수에 따라 2의 제곱수로 최대 100제곱까지 늘어나게 되어 주어진 10초의 제한시간으로도 통과하지 못한다. 이를 해결하기 위해선 비숍의 가능한 이동 경로와 체스판의 격자 무늬를 생각하면 시간을 절반으로 줄일 수 있는 아이디어를 떠올릴 수 있다. 비숍은 대각선으로만 이동할 수 있기 때문에 흰색 영역에서의 움직임은 검은 영역에 영향을 주지 않고 반대의 경우도 마찬가지다. 따라서 색깔별로 나누어 경우의 수를 구해 서로 더하면 각 단계별로 호출되는 경우의 수가 절반으로 줄어들게 된다.

2의 50제곱도 매우 큰 수이지만 비숍을 놓을 때 마다 놓지 못하게 되는 위치를 체스판에 기록해나가면 경우의 폭이 빠르게 줄어들어 제한시간안에 통과할 수 있다. 비숍을 놓을 수 있는 색칠된 칸은 1, 그렇지 않은 칸은 0으로 주어지는데, 비숍이 놓일 수 있는 위치인지를 구별하기 위한 값으로 사용될 수 있다. 체스판의 값이 1일 경우에만 비숍을 놓고, 이동할 수 있는 경로의 값들을 모두 1씩 증가시키면 된다.