[BAE/<JOON> 문제풀이] 1799. 비숍

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

1799번: 비숍

핵심::
완전탐색 최적화

풀이::
보자마자 생각 할 수 있는 풀이 :
모든 판에 비숍을 배치하며 배치의 유효성을 검사하는 방법이 있다. ( 복잡도 O(2^n) )
하지만 체스판이 64칸이므로 시간 안에 동작할 수 없다.

아이디어를 떠올리기 : 
비슷한 문제 N퀸은 왜 간단하게 풀 수 있었나 생각해보자

퀸은 대각선 뿐만 아니라 같은 종 / 횡에도 하나씩밖에 배치 할 수 없다.

그렇기 때문에 각 행마다 하나의 퀸을 배치하면 그 행에서의 탐색은 종료하고 다음 탐색을 진행 할 수 있다.

비숍은 대각에 하나씩밖에 배치 할 수 없으니 이 점을 활용하기 위해 체스판을 45도 회전시켜 서로 대각선을 공유하는 2개의 그룹으로 분리해보자.

체스판

빨간 타일과 파란 타일은 대각선으로 봤을 때 완전히 분리된 타일들이다. 즉, 빨간 타일과 파란 타일에 배치할 수 있는 비숍의 최대 개수를 구하여 합치면 답을 구할 수 있다.

또한 타일을 45도 회전시켰으므로 해당 자리에 배치할 수 있는지 없는지 판단하는 로직도 매우 간단하다.

의견::
평범한거 같았는데 아이디어 떠울리기 어렵다는 평가가 많아서 기분 좋았음

 

코드:: (코드 더러움 주의)

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

using namespace std;

int arr[11][11];
vector<vector<int>> t, ch;
int mx = -1;
int n;

void r(int x, int cnt) {
	if (x >= n * 2 || mx == 2 * n - 2) {
		if (mx < cnt) {
			mx = cnt;
			/*for (auto v1 : ch) {
				for (auto v2 : v1) {
					cout << v2 << " ";
				}
				cout << "\n";
			}*/
		}

		return;
	}

	for (int i = 0; i < t[x].size(); i++) {
		if (t[x][i] == 1) {
			bool able = true;
			int xc = i;
			for (int j = x - 2; j > 0; j -= 2) {				
				if (j + 1 == n) {}
				else if (j >= n) xc++;
				else if (j < n) xc--;
				
				if (t[j].size() <= xc) break;

				if (ch[j][xc] == 1) {
					able = false;
					break;
				}
			}

			if (able) {
				ch[x][i] = 1;
				r(x + 1, cnt + 1);
				ch[x][i] = 0;
				break;
			}
		}		
	}
	for (int i = t[x].size() - 1; i >= 0; i--) {
		if (t[x][i] == 1) {
			bool able = true;
			int xc = i;
			for (int j = x - 2; j > 0; j -= 2) {
				if (j + 1 == n) {}
				else if (j >= n) xc++;
				else if (j < n) xc--;

				if (t[j].size() <= xc) break;

				if (ch[j][xc] == 1) {
					able = false;
					break;
				}
			}

			if (able) {
				ch[x][i] = 1;
				r(x + 1, cnt + 1);
				ch[x][i] = 0;
				break;
			}
		}
	}
	r(x + 1, cnt);
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}

	t = vector<vector<int>>(n * 2);
	ch = vector<vector<int>>(n * 2);


	for (int i = 1; i <= n; i++) {
		int c1 = i, c2 = 1;
		do {
			t[i].push_back(arr[c1][c2]);
			ch[i].push_back(0);
			c1--;
			c2++;
		} while (c1 >= 1 && c2 <= n);
	}

	for (int i = 2; i <= n; i++) {
		int c1 = n, c2 = i;
		do {
			t[n + i - 1].push_back(arr[c1][c2]);
			ch[n + i - 1].push_back(0);
			c1--;
			c2++;
		} while (c1 >= 1 && c2 <= n);
	}

	r(1, 0);

	cout << mx;

	return 0;
}