[백준 1799번 C/C++] 비숍

 

[백준 1799번 C/C++] 비숍

 

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

1799번: 비숍

---

 

해결전략

 

백트랙킹 Backtracking

---

 

처음 시도한 코드

 

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

int n; // 체스판의 크기 n x n
vector<vector<int>> v;
vector<pair<int, int>> place;
int answer; // 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수

bool CheckDiagonals(int y, int x, vector<vector<int>>& ch)
{
	for (int k = 1; k < n; k++)
	{
		if (y >= k && x >= k && ch[y - k][x - k] == 1) return false;
		if (y >= k && x + k < n && ch[y - k][x + k] == 1) return false;
		if (y + k < n && x >= k && ch[y + k][x - k] == 1) return false;
		if (y + k < n && x + k < n && ch[y + k][x + k] == 1) return false;
	}

	return true;
}

void Calculate()
{	
	int t = place.size();
	while(t--)
	{
		int cnt = 0;
		vector<vector<int>> ch(n, vector<int>(n, 0));
		//vector<vector<int>> tmp(n, vector<int>(n, 0)); // 디버깅용
		for (int i = 0; i < t; i++)
		{
			int y = place[i].first;
			int x = place[i].second;

			if (ch[y][x] == 0 && CheckDiagonals(y, x, ch))
			{
				cnt++;
				ch[y][x] = 1;
				//tmp[y][x] = 5; // 디버깅용
			}
		}
		answer = max(answer, cnt);
		
		//디버깅용
		//cout << "cnt = " << cnt << "\n";
		//for (int y = 0; y < n; y++) {
		//	for (int x = 0; x < n; x++) {
		//		cout << tmp[y][x] << " ";
		//	}
		//	cout << "\n";
		//}
		//tmp.clear();
		//cout << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	if (n == 1) {
		int input;
		cin >> input;
		if (input == 0) { cout << "0"; return 0; }
		else if (input == 1) { cout << "1"; return 0; }
	}

	v.resize(n, vector<int>(n));
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> v[y][x];

			if (v[y][x] == 1) place.push_back({ y, x });
		}
	}

	Calculate();

	cout << answer << "\n";

	return 0;
}

 

 

---

 

정답 코드

 

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

int n; // 체스판의 크기 n x n
vector<vector<int>> v; // 체스판
vector<int> l, r; // 흰색과 검은색 2가지 대각선 방향에 비숍이 존재하는지 여부를 기록하는 벡터
int answer[2]; // 흰색칸, 검은색칸에 놓일 수 있는 비숍의 최대 개수

void BackT(int y, int x, int cnt, int color)
{
	if (x >= n) { // x 좌표가 체스판을 벗어나면 다음 행으로 이동
		y++; // 다음 행으로 이동

		// 시작하는 칸의 색깔에 따라 x 좌표 조정
		if (x % 2 == 0) x = 1;
		else x = 0;
	}

	if (y >= n) { // y 좌표가 체스판을 벗어나면 종료 조건에 도달
		answer[color] = max(answer[color], cnt);
		return;
	}

	// 현재 칸에 비숍을 놓을 수 있는지 확인
	if (v[y][x] && l[x - y + n-1] == 0 && r[y + x] == 0)
	{
		l[x - y + n-1] = 1; // 왼쪽 대각선에 비숍이 있다고 표시
		r[y + x] = 1;		// 오른쪽 대각선에 비숍이 있다고 표시
		BackT(y, x + 2, cnt + 1, color); // 비숍을 놓고 다음 칸으로 이동
		l[x - y + n-1] = 0; // 백트래킹: 왼쪽 대각선 표시 제거
		r[y + x] = 0;		// 백트래킹: 오른쪽 대각선 표시 제거
	}
	BackT(y, x + 2, cnt, color); // 비숍을 놓지 않고 다음 칸으로 이동
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n, vector<int>(n));
	l.resize(n * 2);
	r.resize(n * 2);

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> v[y][x];
		}
	}

	// 비숍 배치를 위한 초기 호출: 흰색 칸과 검은색 칸에 대해 각각 재귀 함수 호출
	BackT(0, 0, 0, 0); // 흰색 칸에서 시작
	BackT(0, 1, 0, 1); // 검은색 칸에서 시작

	// 최종 답 출력: 흰색 칸과 검은색 칸에 놓인 비숍의 최대 개수 합
	cout << answer[0] + answer[1] << "\n"; 

	return 0;
}

 

---