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

1. 문제

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

 

2. 알고리즘 분류

• 백트래킹

 

3. 소스 코드

#include <iostream>
#include <algorithm>
#define MAX_N 10

using namespace std;

int n, ans;
int map[MAX_N][MAX_N];
bool is_visited_upward_right[2 * MAX_N];
bool is_visited_downward_right[2 * MAX_N];

// DFS 알고리즘
void dfs(int diagonal_index, int bishop_cnt) {

	/* 우상향의 대각선의 index를 모두 탐색했을 경우,
	* 우상향의 대각선의 갯수 = 2 * (맵의 크기) - 1
	* n = 5 => 대각선의 갯수 = 9개
	*		1	2	3	4	5		
	*	[0	0	0	0	0]	6
	*	[0	0	0	0	0]	7
	*	[0	0	0	0	0]	8
	*	[0	0	0	0	0]	9
	*	[0	0	0	0	0]
	* 
	*/
	if (diagonal_index >= 2 * n - 1) {
		ans = max(ans, bishop_cnt);
		return;
	}

	// 비숍을 두었는지 여부 확인하는 Flag
	bool flag = false;

	/* 우상향 대각선의 인덱스에서 움직일 수 있는 좌표들 탐색
	* 우상향 대각선의 인덱스에서 칸의 개수 = (맵의 크기) - abs((우상향 대각선 인덱스) - ((맵의 크기) - 1))
	* ex) n = 5, diagonal_index = 0 => 대각선 칸의 갯수 = 1
	*     n = 5, diagonal_index = 1 => 대각선 칸의 갯수 = 2
	*     n = 5, diagonal_index = 2 => 대각선 칸의 갯수 = 3
	*     n = 5, diagonal_index = 3 => 대각선 칸의 갯수 = 4
	*     n = 5, diagonal_index = 4 => 대각선 칸의 갯수 = 5
	*     n = 5, diagonal_index = 5 => 대각선 칸의 갯수 = 4
	*     n = 5, diagonal_index = 6 => 대각선 칸의 갯수 = 3
	*     n = 5, diagonal_index = 7 => 대각선 칸의 갯수 = 2
	*     n = 5, diagonal_index = 8 => 대각선 칸의 갯수 = 1
	*		1	2	3	4	5		
	*	[0	0	0	0	0]	4
	*	[0	0	0	0	0]	3
	*	[0	0	0	0	0]	2
	*	[0	0	0	0	0]	1
	*	[0	0	0	0	0]
	*/
	for (int idx = 0; idx < n - abs(diagonal_index - (n - 1)); idx++) {

		/* y, x좌표 구하는 방법
		* case 1) 우상향 index가 전체 대각선 인덱스의	반 이하일 때,
		*  y 좌표 = diagonal_index - (x좌표)
		*  x 좌표 = idx
		* case 2) 우상향 index가 전체 대각선 인덱스의 반 이상일 때,
		*  y 좌표 = (n - 1) - idx
		*  x 좌표 = diagonal_index - (y 좌표)
		* 
		* ex) n = 5, diagonal_index = 2일 때,
		* idx = 0 => y = 2, x = 0
		* idx = 1 => y = 1, x = 1
		* idx = 2 => y = 0, x = 2
		* 
		* ex) n = 5, diagonal_index = 6일 때,
		* idx = 0 => y = 4, x = 2
		* idx = 1 => y = 3, x = 3
		* idx = 2 => y = 2, x = 4
		*/
		int y = 0;
		int x = 0;
		
		if (diagonal_index < n - 1) {
			x = idx;
			y = diagonal_index - x;
		}
		else {
			y = (n - 1) - idx;
			x = diagonal_index - y;
		}

		/* 우하향 대각선 index 구하는 방법
		* 우하향 대각선 index = (n - 1) + (x - y)
		* 
		* ex) n = 5 일때,
		* y = 4, x = 0 => diagonal_index2 = 0
		* y = 3, x = 0 => diagonal_index2 = 1
		* y = 2, x = 0 => diagonal_index2 = 2
		* y = 3, x = 0 => diagonal_index2 = 2
		* y = 0, x = 0 => diagonal_index2 = 4
		* y = 0, x = 1 => diagonal_index2 = 5
		* y = 0, x = 2 => diagonal_index2 = 6
		* y = 0, x = 3 => diagonal_index2 = 7
		* y = 0, x = 4 => diagonal_index2 = 8
		*/
		int diagonal_index2 = (n - 1) + (x - y);

		// map[y][x] 좌표에 비숍을 둘 수 있는지 체크 및, 우상향 대각선과 우하향 대각선에 비숍이 있는지 확인
		if (map[y][x] == 1 && !is_visited_upward_right[diagonal_index] && !is_visited_downward_right[diagonal_index2]) {
			flag = true;	// 비숍 두었다는 체크
			is_visited_upward_right[diagonal_index] = true;	// 우상향 대각선 비숍 체크
			is_visited_downward_right[diagonal_index2] = true;	// 우하향 대각선 비숍 체크
			dfs(diagonal_index + 1, bishop_cnt + 1);
			is_visited_upward_right[diagonal_index] = false;	// 우상향 대각선 비숍 체크 해제
			is_visited_downward_right[diagonal_index2] = false;	// 우하향 대각선 비숍 체크 해제
		}
	}

	// 해당 대각선 index에 비숍을 안 두었을 경우, 다음 대각선 index로 이동
	if (!flag)
		dfs(diagonal_index + 1, bishop_cnt);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// n : 체스판 크기 입력 
	cin >> n;

	// 체스판 정보 입력
	for (int y = 0; y < n; y++)
		for (int x = 0; x < n; x++)
			cin >> map[y][x];

	// DFS 알고리즘
	dfs(0, 0);

	// 정답 출력
	cout << ans;

	return 0;
}

 

4. 알고리즘

 1) DFS 탐색(깊이 우선 탐색)

https://uigwonblog.tistory.com/75

[알고리즘] DFS (깊이 우선 탐색)