[BOJ 1799] 비숍

문제 링크 : https://www.acmicpc.net/problem/1799

문제 분류 : 백트래킹

참고 : https://j2wooooo.tistory.com/80

 

풀이 방법이 생각이 안나서 참고하면서 풀었다. ㅠ.ㅠ

 

문제 풀이

핵심은 하나는 체스판을 두 부분으로 나누어서 보는 것이다!

위 그림과 같이 체스판을 흰색과 검은색으로 칠하고 보면,

흰색 영역과 검은색 영역은 대각선으로 이동으로는 절대 겹칠 수 없는 영역이다.

 

즉, 하나의 체스판을 2부분으로 나눠서 생각해볼 수 있다.

 

최종적으로

검은색 영역 최대 개수 + 흰색 영역 최대 개수 로 답을 구할 수 있다.

 

한 부분에 대한 시간 복잡도는 다음과 같이 계산될 수 있다.

1. 하나의 칸에 비숍을 놓는경우, 놓지 않는 경우가 존재 => 2가지
2. 흑, 백 각각 N/2, N/2

두 부분으로 나누지 않을 경우 2^(N*N)만큼의 시간 복잡도를 갖게되어 시간 초과가 난다.

두 부분으로 나누게 되면 2^(N*N/2)의 시간 복잡도를 갖게 될것 같지만, 백트래킹을 통해 좀 더 최적화가 일어 난다고 한다.

참고

 

다음과 같은 3가지 경우를 모두 만족하면 비숍을 놓을 수 있다.

1. 비숍을 놓을 수 있는 영역이다.
2. ▧ (오른쪽 아래로 향하는 대각선) 방향에 비숍이 없는 경우
3. ▨ (왼쪽 아래로 향하는 대각선) 방향에 비숍이 없는 경우

위의 경우가 아니라면 비숍을 놓을 수 없으므로 다음 단계를 진행한다. => 그대로 DFS 진행

 

만약 비숍을 놓을 수 있는 경우라면 DFS와 백트래킹을 진행한다.

 

비숍을 놓을 수 있는 영역인지는 입력 값을 통해 구분 가능한데, 대각선 방향 계산은 어떻게 해야할까?

 

위 그림에서 다음과 같은 특징을 도출해 낼 수 있다.

1. ▧ 방향은 col - row의 값이 같다.
2. ▨ 방향은 row + col의 값이 같다.

위와 같이 계산하면 row col 두 값만 있으면 두개의 대각선을 모두 구할 수 있다.

이때, 주의 해야할 점은 ▧ 방향 계산은 음수가 나올 수 있다는 것이다. (row > col 인경우)

col - row의 최소값은 -(N-1) 이므로 col - row 값에 N-1을 더해준 값을 취해서 계산한다.

=> col - row + N - 1 

 

참고)

'x' 모양 대각선을 살짝 회전시켜 '+' 모양을 만들었다고 생각하면 

▧가 '-' 방향 , ▨가 '|' 방향이 된다.

(col, row) -> (col + row, col - row)

 

[구현 코드]

#include<cstdio>

using namespace std;

#define max(a,b) a > b ? a : b

int N;
bool board[10][10];
int ans[2];
int ansIdx;
bool rd[20], ld[20]; //오른쪽 아래 대각선, 왼쪽 아래 대각선

void dfs(int row, int col, int cnt)
{
	if (col >= N)
	{
		row++;
		col = col & 1 ? 0 : 1; //행이 바뀔 때 toggle (0->1, 1->0)
	}
	if (row >= N) // 탐색을 1회 마칠 때마다 
	{
		//기존 count 값과 비교하여 클 경우 값을 갱신 해준다.
		ans[ansIdx] = max(ans[ansIdx], cnt);
		return;
	}

	// 비숍을 놓을 수 있는 경우
	if (board[row][col] && !rd[col + row] && !ld[col - row + N - 1])
	{
		ld[col - row + N - 1] = rd[row + col] = true; // 비숍을 놓았다고 체크
		dfs(row, col + 2, cnt + 1); // 현재 비숍을 놓고 탐색하면서 최대 ans를 갱신
		ld[col - row + N - 1] = rd[row + col] = false; // 비숍을 되돌리고(back) 다시 탐색
	}
	dfs(row, col + 2, cnt); // 현재 단계에서 비숍을 놓지 않고 이동 하는 경우
}

int main()
{
	scanf("%d", &N);

	int input = 0;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			scanf("%d", &input);
			board[i][j] = 0 < input;
		}
	}

	dfs(0, 0, 0);
	ansIdx++;
	dfs(0, 1, 0); // 두 그룹의 시작열이 다르다
	printf("%d", ans[0] + ans[1]);
}

다음은 알고리즘에 대한 설명이다.

1. 현재 위치에 비숍을 놓을 수 있는 경우,
   1. 두개의 대각선에 다른 비숍을 놓을 수 없도록 세팅한다.
   2. 현재 위치에 비숍을 놓고 다음 단계를 진행 => 카운트 값은 1증가, 가로 방향으로 2칸 이동하는 경우로 탐색
   3. 2 탐색을 마치고 돌아왔을 때 비숍을 놓지 않는 경우로 확인 해야 하므로 대각선 세팅 갑을 푼다
2. 비숍을 놓지 않는 경우, 열 방향으로 2칸 움직이고 다음 단계를 진행한다.
3. 가로 방향 인덱스가 범위를 넘어 선 경우, 행을 증가 시키고, 열 값은 toggle(0->1, 1->0)시킨다. 만약, 증가된 행이 인덱스 범위를 넘어 섰다면 1회 탐색이 끝난것이기 때문에 현재 비숍 갯수와 이전 비숍 개수를 비교하여 큰 값으로 갱신한다. 그리고 이전 단계로 되돌아간다.
4. 모든 경우에 대해 탐색할 때까지 1~3을 반복하면서 놓을 수 있는 최대 비숍 개수를 갱신한다.