비숍

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
10 초	128 MB	22527	5606	3885	24.324%

문제

서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다.

< 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때

비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.

그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다.

< 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자.

이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다. 

색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.

정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다.

체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때,

서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 크기가 주어진다.

체스판의 크기는 10이하의 자연수이다.

둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다.

비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.

출력

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

예제 입력 1

5
1 1 0 1 1
0 1 0 0 0
1 0 1 0 1
1 0 0 0 0
1 0 1 1 1

예제 출력 1

7

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2007 > 초등부 5번

알고리즘 분류

• 백트래킹

---

비숍은 같은 색깔의 비숍만 잡을 수 있다.

다른 색에 있는 비숍까지 모든 경우의 수를 고려한다면 시간 초과가 발생

아래의 코드는 재귀적으로 BackTracking을 구현한 코드

N x N 크기의 체스판에서 N개의 퀸을 배치하는 모든 경우를 탐색

각 칸마다 O(N) 시간이 소요되고, N x N 크기의 체스판에 N개의 퀸을 배치하므로

총 시간 복잡도는 O(N^N) => 시간초과

시간 초과 코드

#include <iostream>
using namespace std;
constexpr int _MAX = 10;
int _N, _Res;
bool _Map[_MAX][_MAX];
bool _Dx[19], _Dy[19];

void BackTracking(int _Cnt, int _x)
{
	int _dxy, _sum;
	for (int i = _x; i < _N; i++)
		for (int j = 0; j < _N; j++) {
			if (!_Map[i][j]) continue;
			_dxy = i - j + _N - 1;
			_sum = i + j;
			if (_Dx[_dxy] || _Dy[i + j]) continue;
			_Dx[_dxy] = true;
			_Dy[_sum] = true;
			BackTracking(_Cnt + 1, i);
			_Dx[_dxy] = false;
			_Dy[_sum] = false;
		}

	_Res = max(_Res, _Cnt);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _N;
	for (int i = 0; i < _N; i++)
		for (int j = 0; j < _N; j++)
			cin >> _Map[i][j];
	BackTracking(0, 0);
	cout << _Res;
	return 0;
}

통과된 코드

아래의 코드는 하얀 칸에 올 수 있는 비숍의 최댓값과

검은칸에 올 수 있는 비숍의 최댓값을 따로 구한 후 합한 결과를 출력해준다.

비숍을 해당 칸에 놓는 경우 / 안 놓는 경우 => 2가지

N / 2 칸을 N^2으로 탐색하지만 흑/백 2번이므로 => N^2

약 O(2^N^2)의 시간 복잡도를 가진다.

#include <iostream>
using namespace std;
constexpr int _MAX = 10;
int _N, _Res, _ResSum;
bool _Map[_MAX][_MAX];
bool _CheckX[19], _CheckY[19];

void CheckBishop(int _bishopCnt, int _x, bool _isOdd)
{
	int _dxy, _sum;
	for (int i = _x; i < _N; i++)
		for (int j = 0; j < _N; j++) {
			if (!_Map[i][j]) continue;
			_dxy = i - j + _N - 1;
			_sum = i + j;
			if (_CheckX[_dxy] || _CheckY[i + j] || _sum % 2 == _isOdd) continue;
			_CheckX[_dxy] = true;
			_CheckY[_sum] = true;
			CheckBishop(_bishopCnt + 1, i, _isOdd);
			_CheckX[_dxy] = false;
			_CheckY[_sum] = false;
		}

	_Res = max(_Res, _bishopCnt);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _N;
	for (int i = 0; i < _N; i++)
		for (int j = 0; j < _N; j++)
			cin >> _Map[i][j];
	CheckBishop(0, 0, false);
	_ResSum += _Res;
	_Res = 0;
	CheckBishop(0, 0, true);
	_ResSum += _Res;
	cout << _ResSum;
	return 0;
}

제출된 답 중에서 0ms 도 있다… 세상에는 괴물이 많다.