[백준/알고리즘] 1799번 비숍 (골드 2)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 1799번

 

크기가 N x N인 체스판이 있다. 체스판 위에는 말을 올릴 수 없는 칸이 표시되어 있다.
이 체스판 위에 비숍(bishop)을 최대한 많이 올려두려고 한다. 한번에 올릴 수 있는 비숍의 최대 개수를 출력하시오.

 

풀이 알고리즘 : 백트래킹

 

이 문제를 풀기 전에, N-Queen 문제를 풀었기 때문에, 해당 문제와 똑같이 백트래킹으로 풀려고 시도했다.

그러나 이번 문제와 다른 점은, 퀸은 8방향 모두 공격할 수 있기 때문에, 한 줄에 하나의 퀸만 놓을 수 있었고, 이번 문제에서는 비숍이기 때문에 같은 줄에 여러개의 비숍이 존재할 수 있는 것이다.

 

백준 1799번

즉 보드의 길이 N이 적어졌더라도, 실제로 계산해야 하는 양이 많아져서, 같은 방법으로 풀면 시간 초과에 걸릴 수 밖에 없다.

 

이때 비숍의 특성을 생각해보자. 체스판이 검정칸과 하얀칸이 있다면, 비숍은 대각선으로만 움직이므로, 원래 있던 색과 다른 색의 칸으로 이동하지 못한다. 이를 코드에서 생각한다면, x좌표와 y좌표의 합이 홀수인 칸과, 짝수인 칸 중 하나의 종류의 칸에서만 이동할 수 있다.

 

백준 1799번

그래서 다시 정리해보면, (i + j)가 짝수이면 검정칸, 홀수이면 하얀칸에 위치한다. 그래서 백트래킹을 실행하면서, 칸을 두칸씩 건너뛰어서 같은 색의 칸만 탐색하도록 확인해주었다.

 

주의해야할 점은 y좌표가 바뀔 때 마다, 시작하는 x좌표의 값이 1과 2가 번갈아가면서 나오는 부분을 잘 처리를 해주어야 한다.

 

위와같은 처리를 해주면, 최대 범위 10 X 10에서 찾아야 하는 비숍의 갯수를 5 X 5 + 5 X 5로 나눌 수 있고, 시간제한에도 물론 걸리지 않는다.

 

이후부터는 칸의 색깔에 맞춰서 백트래킹을 하여 모든 경우를 탐색하여 최댓값을 찾았다. 이 경우 N-Queen문제와 동일하게 현재 y좌표보다 위에 있는 비숍을 확인하여 해당 비숍의 y좌표와, 현재 위치의 y좌표의 차이가 해당 비숍의 x좌표와 현재 위치의 x좌표의 차가 같다면 놓을 수 없음을 처리하면 된다. (대각선은 기울기가 1인 그래프이다.)

백준 1799번

 

아래는 제출코드이다.

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

// 전역변수
int n, b, ans;
int check[15 + 1][15 + 1];

// 조건 내의 위치인지 검사
bool inRange(int y, int x) {
	return (0 < y && y <= n && 0 < x && x <= n);
}

int solve(int y, int x, int cnt) {
	// 범위를 벗어난다면 탐색 종료
	if(!inRange(y, x)) return cnt;

	int ret = 0;
	bool isE = ((x + y) % 2 == 0);

	// 이동할 수 있는 다음 칸을 탐색
	int xx = x + 2;
	int yy = y;
	
	// 다음 칸의 좌표 설정
	if(isE && (n < xx)) {
		if(yy % 2 == 0) {
			yy++; xx = 1;
		} else {
			yy++; xx = 2;
		}
	} else if(!isE && (n < xx)) {
		if(yy % 2 == 0) {
			yy++; xx = 2;
		} else {
			yy++; xx = 1;
		}
	}

	if(check[y][x] == 0) {
		// 현재 칸에 놓을 수 있는지 확인
		bool one = false;
		bool canPlace = true;
		for(int i = 1; i < y; i++) {
			one = !one;
			if(isE) {
				for(int j = (one ? 1 : 2); j <= n; j += 2) {
					if(check[i][j] == 1 && abs(i - y) == abs(j - x)) {
						canPlace = false;
						break;
					}
				}
			} else {
				for(int j = (one ? 2 : 1); j <= n; j += 2) {
					if(check[i][j] == 1 && abs(i - y) == abs(j - x)) {
						canPlace = false;
						break;
					}
				}
			}
		}

		// 현재 칸에 놓을 수 있으면, 놓은 후 다음 칸 탐색
		if(canPlace) {
			check[y][x] = 1;
			ret = max(ret, solve(yy, xx, cnt + 1));
			check[y][x] = 0;
		}
	}

	// 현재 칸에 놓지 않은 경우, 다음 칸 탐색
	ret = max(ret, solve(yy, xx, cnt));

	return ret;
}

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			cin >> b;
			if(b == 0) {
				check[i][j] = 100;
			}
		}
	}

	ans = solve(1, 1, 0);
	ans += solve(1, 2, 0);
	cout << ans;

	return 0;
}