[백준] 1799번: 비숍

📌 문제

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

📌 설명

9663번: N-Queen 문제와 유사한 문제이다. 역시 백트래킹으로 해결하는 문제이고, 시간 초과가 발생하지 않게 효과적으로 구현하는 것이 목적이다.

핵심 아이디어는 ‘서로 다른 두 비숍은 같은 대각선 상에 위치할 수 없다.’이다. 처음에는 비숍이 위치할 수 있는 좌표들을 단순히 벡터 coor에 저장하고 백트래킹 함수에서 coor을 순회하며 현재 접근하는 좌표를 지나는 우상향, 우하향 대각선 상에 다른 비숍이 위치하는지를 확인했다. 그러나 현재 백트래킹 함수에서 coor[i]에 접근했다면 다음 백트래킹 함수에는 coor[i + 1]에 접근하도록 하여 불필요한 접근을 최소화하였지만 계속 시간 초과가 발생하였다.

시간 초과가 발생한 이유는 가능한 좌표들을 행 단위로 접근했다는 점이다. i번 째 우상향 대각선을 지나는 좌표들이 저장된 벡터를 board라고 하고 i = 0인 우상향 대각선은 (0, 0)을 지난다고 하자. 즉, i = n - 1인 우상향 대각선은 (n - 1, n - 1)을 지난다. 만약 백트래킹 함수에서 board[i]에 접근했다면 다음 백트래킹 함수는 board[i + 1]에 접근하는 것이 이전보다 불필요한 접근을 최소화할 수 있을 것이다.

현재 접근하는 좌표가 (x, y)일 때, 해당 좌표를 지나는 우상향 대각선의 인덱스는 x + y, 우하향 대각선의 인덱스는 x - y + n - 1로 설정했다. 이때 0번째 우상향 대각선은 (0, 0)을 지나며 0번째 우하향 대각선은 (0, n - 1)을 지난다. 이 부분은 본인 편한 대로 설정해도 무방할 듯하다.

체스판의 크기가 $N \times N$일 때, 우상향 대각선은 총 $2N-1$개 존재한다. 각 우상향 대각선은 최대 $N$개의 셀이 포함될 수 있다. 최악의 경우는 모든 셀에 비숍을 배치할 수 있는 경우이며(모든 셀이 1인 경우), 각 우상향 대각선에 $N$개의 셀이 존재하는 경우이다. 각 우상향 대각선에서 $N$개의 선택지가 존재하며, 우상향 대각선의 특정 좌표를 지나는 우상향/우하향 대각선을 지나도록 처리한다. 그러나 같은 우상향 대각선 내 좌표들은 같은 우상향 대각선을 공유하므로 하나의 우상향 대각선에는 최대 1개의 비숍만 배치할 수 있다. 즉, 각 단계에서 비숍 배치 시도 횟수는 1회로 제한된다.

총 $2N-1$번의 재귀가 수행되며, 각 단계별 분기의 수는 1회로 간주할 수 있다. 따라서 시간복잡도는 $O(2^N)$이다.

📌 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<pair<int, int>> board[20]; // board[i]: i번 째 우상향 대각선을 지나는 좌표들, i = 0은 (0, 0)을 지남, i = x + y
int ans = 0;
int rightUp[20];
int rightDown[20];

void bt(int k, int idx) {
	if (idx >= 2 * n - 1) {
		ans = max(ans, k);
		return;
	}

	bool flag = false;
	for (int i = 0; i < board[idx].size(); i++) {
		int x = board[idx][i].first;
		int y = board[idx][i].second;

		if (!rightUp[x + y] && !rightDown[x - y + n - 1]) {
			flag = true;
			rightUp[x + y] = 1;
			rightDown[x - y + n - 1] = 1;
			bt(k + 1, idx + 1);
			rightUp[x + y] = 0;
			rightDown[x - y + n - 1] = 0;
		}
	}

	if (!flag) {
		bt(k, idx + 1);
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int x;
			cin >> x;
			
			if (x) {
				board[i + j].push_back({i, j});
			}
		}
	}

	bt(0, 0);
	cout << ans;
}