BOJ 1799 - 비숍 (🔄)

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

1799번: 비숍

 

접근 방법

10초라고해서 기존 백트래킹을 이용했는데 10X10에선 시간초과가 났다.

 

비숍을 둘 수 있는 곳을 따로 저장하여 recursion 속 for문에서 사용하였는데 , 중복되는 부분이 많았다.

recursion을 비숍을 둘 수 있는 곳을 기준으로 도는 것이 아니라 x,y를 기준으로 돌면 좋겠다는 생각을 하루동안 하지 못했다...

따라서, 다른 블로그를 참고하였다.

 

문제의 핵심은 다음과 같다.

1. parameter에 row와 col을 사용하여 recursion을 한다.

2. 밑의 그림처럼 black과 white를 나눠서 계산하고, 두 개를 더한 값을 구한다.

출처: https://j2wooooo.tistory.com/80

 

2번을 유심히 생각해보자.

비숍의 경우 대각선으로만 서로 영향을 미치기 때문에, black과 white 간의 간섭은 발생할 수 없다.

만약 이를 고려하지 않고 진행하면 O(n^2)으로 브루트포스와 같은 실행시간이 소요된다.

 

그러나 color을 나눠서 계산하면 O(N/2 * N/2)로 Time Complexity가 확실히 감소하기에 시간초과를 벗어날 수 있다.

 

블로그 글쓰신 분들 대단하십니다...

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

#define MAX 200

using namespace std;

int n;
bool chk1[MAX];
bool chk2[MAX]; 
int map[MAX][MAX];
int res[2];

// 비숍을 둘 수 있는 칸의 남은 개수
void func(int row, int col, int bishop, int color) {
	//cout << "cnt: " << cnt << endl;
	if (col >= n) {
		row++;
		if (col % 2 == 0)	col = 1;
		else	col = 0;
	}
	if (row >= n) {
		res[color] = max(res[color], bishop);
		return;
	}

	// 둘 수 없으면 패스
	if (!map[row][col] || chk1[row + col] || chk2[row - col + n - 1]) {
		func(row, col + 2, bishop, color);
	}
	else {
		chk1[row + col] = true;
		chk2[row - col + n - 1] = true;
		func(row, col + 2, bishop + 1, color);
		chk1[row + col] = false;
		chk2[row - col + n - 1] = false;

		func(row, col + 2, bishop, color);
	}
}

int main() {
	ios::sync_with_stdio(false);
	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];
		}
	}
	
	func(0, 0, 0, 0);
	func(0, 1, 0, 1);
	cout << res[0] + res[1];
}