🎲문제

주소:백준 1799

서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.

< 그림 1 >

그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다.  색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.

< 그림 2 >

< 그림 3 >

정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.

⌨ 입력

첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.

✅ 풀이

풀이방법

DFS를 활용한 백트래킹 문제이다. 단순히 DFS를 사용하는 것 뿐만 아니라 어떻게 하면 더 시간을 줄일수 있는지 고민 해야하는 문제였다. 초기엔 단순히 놓을 수 있는 모든 배열을 접근하여 DFS를 돌리는 방식으로 접근했지만 시간초과를 받았다. 여기저기 검색하고 찾아본 결과, 체스판의 흰색 과 검은색 타일의 비숍은 서로 충돌할 일이 없으므로 흰타일, 검은 타일 두 가지 경우로 나누어 더한다면, N/2의 시간단축 효과를 볼 수 있었다.

1. 체스 보드의 넓이 N을 입력받고 전체 타일 정보를 입력받는다.
2. 흰 타일에 비숍을 배치하는경우(v), 검은 타일에 비숍을 배치하는경우(v2), 두가지 경우로 벡터를 생성하여 배치가 가능한 위치일 때 벡터에 좌표를 집어 넣는다.

void init() {
	cin >> N;

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

			if (num == 1) {
				if (((i + j) % 2) == 1) v.push_back({ i, j });
				else v2.push_back({ i, j });
			}
		}
	}
}

3. v.size()와 v2.size() 각각 dfs를 따로 돌려준다.
4. 각 결과를 저장하여 더함으로써 결과를 출력 할 수 있다.

void solve() {

	for (int i = 0; i < v.size(); i++) dfs(i, 0, v);
	
	int tmp = result;
	result = 0;
	for (int i = 0; i < v2.size(); i++) dfs(i, 0, v2);

	cout << result + tmp;
}

5. 벡터의 인덱스값, 벡터, 비숍의 개수를 인자로 받는 dfs함수를 작성한다.
6. 인덱스값이 벡터의 사이즈만큼 왔을 때(모든 가능한 경우를 순회했을 때), 순회했을 때 비숍의 개수와 기존 비숍 최댓값을 비교해서 더 큰값을 저장한다.
7. 해당 인덱스의 좌표가 비숍이 위치 가능한 좌표인 경우, board에 표시하고 인덱스 크기, 비숍의 개수를 추가해서 dfs를 실행한다.
8. 또한 인덱스가 마지막 값이 아닌 모든경우에도 인덱스 값을 증가시켜 dfs함수로 순회한다.

void dfs(int index, int cnt, vector<pair<int, int>> v ) {

	if (index == v.size()) {
		result = max(cnt,result);
		return;
	}

	int x = v[index].first;
	int y = v[index].second;

	if (chk_bishop(x, y)) {
		board[x][y] = -1;
		dfs(index + 1, cnt + 1, v);
		board[x][y] = 1;
	}

	dfs(index + 1, cnt, v);

	return;
	}

전체 코드

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

using namespace std;

int N, result;
vector<pair<int, int>> v;
vector<pair<int, int>> v2;
int board[10][10] = {0,};
int direction[4][2] = { {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };

void init();
void solve();
void dfs(int, int, vector<pair<int, int>>);
bool chk_bishop(int, int);
bool is_inside(int);

void init() {
	cin >> N;

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

			if (num == 1) {
				if (((i + j) % 2) == 1) v.push_back({ i, j });
				else v2.push_back({ i, j });
			}
		}
	}
}

void solve() {

	for (int i = 0; i < v.size(); i++) dfs(i, 0, v);
	
	int tmp = result;
	result = 0;
	for (int i = 0; i < v2.size(); i++) dfs(i, 0, v2);

	cout << result + tmp;
}

void dfs(int index, int cnt, vector<pair<int, int>> v ) {

	if (index == v.size()) {
		result = max(cnt,result);
		return;
	}

	int x = v[index].first;
	int y = v[index].second;

	if (chk_bishop(x, y)) {
		board[x][y] = -1;
		dfs(index + 1, cnt + 1, v);
		board[x][y] = 1;
	}

	dfs(index + 1, cnt, v);

	return;
}

bool chk_bishop(int x, int y) {

	for (int i = 1; i < N; i++) {
		for (int j = 0; j < 4; j++) {
			int tmp = x + (direction[j][0] * i);
			int tmp2 = y + (direction[j][1] * i);
			if (is_inside(tmp) && is_inside(tmp2)) {
				if (board[x + (direction[j][0] * i)][y + (direction[j][1] * i)] == -1)
					return false;
			}
		}
	}
	return true;
}

bool is_inside(int x) {
	return (0 <= x && x < N);
}

int main() {
	init();
	solve();

	return 0;
}