백준 1799 비숍

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

1799번: 비숍

 

탐색계의 절대강자가 나타났다... 시간 제한이 무려 10초라서, '아~ 시간제한 신경 안써도 되겠네'라고 생각하기 쉽다. 게다가 Input의 최대치가 10이라니?! N! 을 해도 10초는 통과할 수 있다! 

 

하지만... 그냥 완전탐색했다가는 나처럼 좌절을 겪고 모든 코드를 삭제하는 수모를 감내해야만 한다.

 

O(2^(N*N))이었던가... 그렇다.

 

이 문제를 두 가지로 생각할 수 있다

 

1. 이미 있는 비숍을 들어낸다.(모든 가능한 칸에 비숍이 있다고 가정하고, 대각선에 있는 비숍을 제거하는 방식)

2. 비숍을 새로 놓는다. 

 

처음엔 1번 처럼 접근했다가, 탈탈 털렸다. 2번으로 접근하자. 

 

이 문제를 푸는 핵심은 Divide and Conquer 다. 흑색과 백색을 독립적인 세계로 간주하고 풀면 시간복잡도를 줄일 수 있다.(그래도 크긴 크다, 괜히 10초 준게 아니다)

 

/* 1799 비숍 */

#include <iostream>
#include <algorithm>

#define BLACK 0
#define WHITE 1

using namespace std;

void input();
void solve();

int dr[4] = { -1,-1,1,1 };
int dc[4] = { -1,1,1,-1 };
int N, ANS[2];

bool chess[10][10];
bool is_visit[10][10];


int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	input();
	solve();
	
	return 0;
}

void input() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> chess[i][j];
		}
	}
}

/* 너가 원하는 칸에 비숍을 넣을 수 있는지 simulation한다 */
/* 가능하면 true, 불가능하면 false*/
bool simulation(int r, int c) { 
	if (chess[r][c] == false) return false;

	for (int i = 0; i < 4; i++) {
		int nr, nc;
		nr = r; nc = c;

		while (true) {
			nr += dr[i];
			nc += dc[i];

			if (!(nr >= 0 && nr < N && nc >= 0 && nc < N))
				break;
			if (is_visit[nr][nc] == true)
				return false;
		}
	}
	return true;
}

void b_t(int r, int c, int cnt, int color) { // back tracking 줄여서 b_t라고 한다
	if (c >= N) { // C가 범위를 벗어나면 다음 행으로 가야한다. 
		r++; 
		if (r % 2 == 0) c = (color == BLACK ? 0 : 1);
		else c = (color == BLACK ? 1 : 0);
	}

	if (r >= N) { // 탐색 종료
		ANS[color] = max(ANS[color], cnt);
		return;
	}

	if (simulation(r,c) == true) { // 지금 이 칸에 비숍을 넣을 수 있는가?
		is_visit[r][c] = true;
		b_t(r, c + 2, cnt + 1, color); // 이 칸에 비숍 넣었으니까 +1 하기!
		is_visit[r][c] = false;
	}

	b_t(r, c + 2, cnt, color);
}

void solve() {
	// b_t( row, column, count, color) << 요런 매개변수다.
	b_t(0, 0, 0, BLACK); // Black
	b_t(0, 1, 0, WHITE); // WHITE

	cout << ANS[0] + ANS[1];
}