[백준 - 1799] 비숍 - C++, Python

분류: 백트래킹 /

 

문제

문제 링크

문제 설명

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

< 그림 1 >

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

< 그림 2 >

< 그림 3 >

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

입력

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

출력

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

 

풀이

- C++

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

enum color {BLACK, WHITE};
struct xy {int x, y;};

int n, ans[2];
vector<xy> B[2];
bool diag[2][2][20]; // [color][0]: +, [color][1]: -

void backtracking(color c, int cur, int cnt) {
    if(cur == B[c].size()) {
        if(cnt > ans[c]) ans[c] = cnt;
        return;
    }
    if(cnt + B[c].size() - cur <= ans[c]) return;

    if(diag[c][0][B[c][cur].x + B[c][cur].y] or diag[c][1][B[c][cur].x - B[c][cur].y + n]) {
        backtracking(c, cur+1, cnt);
        return;
    }
    
    diag[c][0][B[c][cur].x + B[c][cur].y] = diag[c][1][B[c][cur].x - B[c][cur].y + n] = true;
    backtracking(c, cur+1, cnt+1);
    diag[c][0][B[c][cur].x + B[c][cur].y] = diag[c][1][B[c][cur].x - B[c][cur].y + n] = false;
    backtracking(c, cur+1, cnt);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    bool isB;
    for(int x=0; x<n; x++) {
        for(int y=0; y<n; y++) {
            cin >> isB;
            if(isB) B[(x ^ y) & 1].push_back({x, y});
        }
    }
    
    backtracking(BLACK, 0, 0);
    backtracking(WHITE, 0, 0);
    cout << ans[BLACK] + ans[WHITE];
}

문제를 보자마자 처음 든 생각은 "N-Queen 문제네. 백트래킹으로 풀면 되겠다."

하지만 시간초과가 났다. 아무리 생각해도 다른 비선형 자료구조를 사용해서 시간복잡도를 낮추기 힘들어 보였고 문제의 사이즈를 줄일 수 있나 생각했다.

 

핵심 아이디어는 체스에서 비숍은 흰색 칸과 검은색 칸 둘 중 하나만 다닌다는 것이다.

검은 칸에 놓인 비숍은 흰 칸의 비숍과 독립적이므로 N x N 문제를 검은 칸과 흰 칸에 대한 두 개의 N/2 X N/2 문제로 쪼갤 수 있다.

검은 칸에 놓을 수 있는 비숍의 최댓값과 흰 칸의 최댓값을 구해 더하면 답이다.

 

대각선을 체크하는 방법은 이전에 [백준 - 9663] N-Queen 문제에서 대각선 배열을 이용해 체크하는 법을 익힌 적 있다. 기울기가 음수인 대각선(`diag[c][1]`)의 경우 `x - y + n - 1`이 정확한 0-index이지만 빼기 연산을 굳이 할 필요가 없어 배열의 크기를 키우고 `x - y + n`으로 1-index로 사용했다.

 

`if(cnt + B[c].size() - cur <= ans[c]) return;`의 의미는 남은 모든 칸에 비숍을 놓아도 현재 최대치보다 작을 경우 탐색을 종료하여 탐색 범위를 좁히는 테크닉으로 없어도 무방하다.

 

- Python

import sys
readline = sys.stdin.readline

N = int(readline())
board = [list(map(int, readline().split())) for _ in range(N)]
diagonals = [[[False] * (2 * N) for _ in range(2)] for _ in range(2)]

ans = [0, 0]
candidates = [[], []]
for i in range(N):
    for j in range(N):
        if board[i][j] == 1:
            candidates[(i ^ j) & 1].append((i, j))

def backtracking(color, cur, cnt):
    if cur == len(candidates[color]):
        ans[color] = max(ans[color], cnt)
        return
    
    if cnt + len(candidates[color]) - cur <= ans[color]:
        return
    
    x, y = candidates[color][cur]
    if diagonals[color][0][x + y] or diagonals[color][1][x - y + N]:
        backtracking(color, cur + 1, cnt)
        return
    
    diagonals[color][0][x + y] = diagonals[color][1][x - y + N] = True
    backtracking(color, cur + 1, cnt + 1)
    diagonals[color][0][x + y] = diagonals[color][1][x - y + N] = False
    backtracking(color, cur + 1, cnt)

backtracking(0, 0, 0)
backtracking(1, 0, 0)
print(ans[0] + ans[1])