1799번 비숍

Posted Aug 10, 2025

By matin1202

6 min read

1799번 비숍

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

풀이: 비숍 문제의 효율적인 해결 전략

이 문제는 체스판에 비숍을 놓을 수 있는 최대 개수를 찾는 문제입니다. 비숍은 대각선 방향으로 움직이며, 서로 공격할 수 없는 위치에 놓아야 합니다. 이 문제를 해결하기 위해 백트래킹(Backtracking) 알고리즘과 특정 최적화 기법을 사용합니다.

백트래킹 접근 방식:

문제 분할: 체스판을 흑백으로 나누었을 때, 흑색 칸에 놓인 비숍과 백색 칸에 놓인 비숍은 서로 공격할 수 없습니다. 따라서 전체 문제를 흑색 칸에 비숍을 놓는 문제와 백색 칸에 비숍을 놓는 문제, 두 개의 독립적인 부분 문제로 분리하여 각각 최대 비숍 개수를 구한 후 합산합니다. 이 방법은 탐색 공간을 크게 줄여줍니다.
상태 정의:
- board[x][y]: 현재 (x, y) 칸이 비숍을 놓을 수 있는 칸인지 (1) 없는 칸인지 (0) 나타냅니다.
- rldiag[sum]: x + y 값이 sum인 대각선(오른쪽 아래 방향)에 이미 비숍이 놓였는지 여부를 나타냅니다.
- lrdiag[diff]: x - y + N - 1 값이 diff인 대각선(왼쪽 아래 방향)에 이미 비숍이 놓였는지 여부를 나타냅니다. N - 1을 더하는 이유는 x - y 값이 음수가 될 수 있기 때문입니다.
- cnt: 현재까지 놓은 비숍의 개수.
- x, y: 현재 탐색 중인 체스판의 칸 좌표.
- color: 현재 탐색 중인 칸의 색깔 (0: 흑색, 1: 백색).
백트래킹 과정:
- backtracking(board, cnt, x, y, color) 함수는 현재 (x, y) 칸에서 비숍을 놓을지 말지 결정하고 다음 칸으로 넘어갑니다.
- 기저 조건: x == N (모든 행을 탐색 완료)이면 현재 cnt 값을 maxBishop과 비교하여 최대값을 갱신하고 함수를 종료합니다.
- 재귀 단계:
  - 현재 (x, y) 칸이 color에 해당하는 색깔이고, 비숍을 놓을 수 있는 칸이며 (board[x][y] == 1), 해당 칸의 두 대각선(rldiag, lrdiag)에 아직 비숍이 없는 경우:
    1. 해당 칸에 비숍을 놓습니다 (rldiag[x+y] = true, lrdiag[x-y+N-1] = true).
    2. cnt를 1 증가시키고 다음 칸 (x, y+1)으로 재귀 호출합니다.
    3. 백트래킹을 위해 비숍을 놓았던 상태를 되돌립니다 (rldiag[x+y] = false, lrdiag[x-y+N-1] = false).
  - 현재 칸에 비숍을 놓지 않거나 놓을 수 없는 경우:
    1. cnt를 그대로 유지하고 다음 칸 (x, y+1)으로 재귀 호출합니다.
최종 결과:
- backtracking 함수를 color = 0 (흑색 칸)에 대해 한 번 실행하여 white (흑색 칸의 최대 비숍)를 구합니다.
- maxBishop을 0으로 초기화한 후, color = 1 (백색 칸)에 대해 다시 실행하여 maxBishop (백색 칸의 최대 비숍)을 구합니다.
- 최종 답은 white + maxBishop 입니다.

시간 복잡도: 이론적인 최악의 경우 시간 복잡도는 \(O(2^{N^2})\) 이지만, 실제로는 대각선 체크를 통한 효율적인 가지치기와 흑백 칸 분리(체스판 색칠)를 통해 탐색 공간이 크게 줄어듭니다. 따라서 N=10과 같은 작은 N 값에 대해 충분히 빠른 시간 내에 해를 찾을 수 있습니다.

공간 복잡도: \(O(N^2)\) board 이차원 배열이 N*N 크기의 공간을 사용하고, rldiag와 lrdiag 배열은 각각 O(N) 크기의 공간을 사용합니다. 재귀 호출 스택의 깊이는 한 색깔에 대해 최대 N*N/2이므로, 전체 공간 복잡도는 O(N^2)입니다.

코드

1799.cpp

#include <bits/stdc++.h>
using namespace std;
constexpr int dx[] = {-1, 1, -1, 1};
constexpr int dy[] = {-1, -1, 1, 1};
int maxBishop = 0;
int N;
vector<bool> rldiag, lrdiag;
void backtracking(vector<vector<int>>& board, int cnt, int x, int y, int color){
    if(y == N){
        x++;
        y = 0;
    }
    if(x == N){
        maxBishop = max(cnt, maxBishop);
        return;
    }
    if((x + y) % 2 == color && board[x][y] == 1 && !rldiag[x + y] && !lrdiag[x - y + N - 1]){
        rldiag[x+y] = true;
        lrdiag[x-y+N-1] = true;
        backtracking(board, cnt+1, x, y+1, color);
        rldiag[x+y] = false;
        lrdiag[x-y+N-1] = false;
    }
    backtracking(board, cnt, x, y+1, color);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    auto board = vector(N, vector(N, -1));
    for(auto& c: board)
        for(auto& e: c)
            cin >> e;
    rldiag = vector(2*N-1, false);
    lrdiag = vector(2*N-1, false);
    backtracking(board, 0, 0, 0, 0);
    int white = maxBishop;
    maxBishop = 0;
    backtracking(board, 0, 0, 0, 1);
    cout << maxBishop + white << '\n';
    return 0;
}

Standard Input (stdin):

C++

BaekJoon

This post is licensed under CC BY 4.0 by the author.

풀이: 비숍 문제의 효율적인 해결 전략

코드

Trending Tags