[BOJ] 1799 비숍

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

1799번: 비숍

알고리즘: Backtracking (brute-force)

 

---

접근:

N-queen 문제랑 비슷한 문제로 brute-force로 접근하였다.

이런 류의 문제는 항상 그렇듯 얼마나 가지치기를 잘하냐에 따라 정답이 갈린다.

(오답의 대부분은 TLE 일 것이다.)

 

 

고로 비숍을 배치한다 했을 때, 왼쪽/오른쪽 대각선 모든 좌표를 일일히 확인하는 것은 상당히 비효율적이며

좀 더 효율적인 방식을 찾아야 한다.

 

그래서 각각의 대각선을 아래 그림과 같이 배열로 만들고 비숍을 놓을 때마다 

해당 배열을 check 하는 방식으로 문제에 접근하였다.

 

허나 첫 제출 때 TLE가 뜨게 되어서 좀 더 최적화시킬 수 있는 방안을 생각해보았다.

 

답은 비숍의 특성에 있었는데 체스판을 잘 관찰해보면,

흰색 칸 위에 있는 비숍들과 검은색 칸 위에 있는 비숍들은 서로 영향을 주지 않는다.

 

흰색 / 검은색을 따로 나누면 관찰해야하는 N이 N/2 로 줄어드니 시간을 많이 줄일 수 있다.

(보통 brute-force 류의 문제들은 N이 1씩 커질 때마다 걸리는 시간이 매우 많이 늘어난다)

 

 

// 1799: 비숍
// fail 1: TLE -> 비숍은 같은 색만 움직일 수 있음 -> 흰색, 검은색 장판 나눠서 실행
#include<iostream>
#include<algorithm>
#define MAX(a,b) (((a)>(b))?(a):(b))
using namespace std;

int N, maxC, ans, c;
bool map[10][10];
bool l_dia[20], r_dia[20]; //check diagonal

void FlagReverse(int y, int x)
{
	l_dia[N-x-1+y] ^= 1;
	r_dia[x+y] ^= 1;
}
bool chkFlag(int y, int x)
{
	if (l_dia[N-x-1+y] || r_dia[x+y] || !map[y][x])
		return 0;
	// Flag On
	FlagReverse(y, x);
	return 1;
}
void putBishop(int idx)
{
	int j;
	if (idx > N*2-1)
	{
		maxC = MAX(maxC, c);
		return;
	}
	if (idx < N)
		j = 0;
	else
		j = idx-N+1;
	
	for (int i = 0; i < N-abs(N-1-idx); ++i)
	{
		if (chkFlag(j, idx-j))
		{
			c++;
			putBishop(idx+2);
			c--;
			// Flag Off
			FlagReverse(j, idx-j);
		}
		j++;
	}
	putBishop(idx+2);	// Don't put bishop
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];
			//map[i][j] = 1;	// worst case
	
	putBishop(0);	// White Field
	ans+=maxC;
	maxC = 0; c = 0;
	putBishop(1);	// Black Field
	ans+=maxC;
	cout << ans;
	return 0;
}

 

 

---

심화문제:

BOJ 2570 비숍2 (최대 유량 이용)

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