[백준] 1799-비숍(C++)

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

1799번: 비숍

 

백트래킹문제입니다. 체스판 크기가 최대 10x10입니다. 그렇기 때문에 가지치기를 통해서 반복 횟수를 줄여주어야 합니다.

• 1. 비숍특성상 검은칸에서 시작하면 검은칸으로만 흰칸에서 시작하면 흰칸으로만 이동가능합니다.
• 2. 그렇기 때문에 흰색과 검은색을 각각 구분합니다. (행 +열이 짝수면 흰색 아니면 홀수면 검은색)
• 2. 각각 비숍을 둘 수 있는지 확인합니다. (abs(arr[cur].y - bitshop[j].y) = abs(arr[cur].x - bitshop[j].x) 면 대각선에 비숍이 있는 것)

 

 

아래는 정답코드입니다. 천천히 확인해보세요.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef struct MyStruct
{
	int y;
	int x;
}chess;
int n = 0, result = 0;
int temp[11][11];
vector <chess> arr; //1인 곳
vector <chess> bitshop; // 비숍저장

void dfs(int cnt, int cur) {// 비숍개수, 현재 탐색 위치 순

	if (cnt > result) {
		result = cnt;
	}
	if (cur == arr.size())
		return;

	//1. 비숍가능한지 검사
	bool jud = true;
	for (int j = 0; j < bitshop.size(); j++) {
		if (abs(arr[cur].y - bitshop[j].y) == abs(arr[cur].x - bitshop[j].x)) {
			jud = false;
			break;
		}
	}
	if (jud == true) { //비숍이 가능하다면 
		bitshop.push_back({ arr[cur].y,arr[cur].x });
		dfs(cnt + 1, cur + 1);
		bitshop.pop_back();
	}
	dfs(cnt, cur + 1);

	return;

}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	int answer = 0;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			cin >> temp[i][j];
			if (temp[i][j] == 1 && (i+j)%2 == 0)
				arr.push_back({ i,j });
		}

	dfs(0, 0);
	answer += result;
	result = 0;
	arr.clear();


	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (temp[i][j] == 1 && (i + j) % 2 == 1)
				arr.push_back({ i,j });
		}
	dfs(0, 0);
	answer += result;
	cout << answer << endl;

	
	return 0;
}