[백준 9663] N-Queen

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

9663번: N-Queen

#include <cstdio>
int N;
int cnt;

int flag_col[15 + 2];
int flag_RD[30 + 2];
int flag_LD[30 + 2];

int chk(int r, int c)
{
	if (flag_col[c]) return false;		// 만약 해당 열에 이미 퀸이 있다면 false 리턴
	if (flag_LD[r - c + (N - 1)]) return false;	// 왼쪽 대각선 위에 퀸이 있다면 false 리턴
	if (flag_RD[r + c]) return false;			// 오른쪽 대각선 위에 퀸이 있다면 false 리턴
	return  true;	// 세 경우가 모두 아니라면 true리턴
}



void DFS(int r)
{
	if (r == N) {		// N번 행 까지 모든 경우의 수를 한 번 탐색 끝냈다면 
		cnt++;		// cnt 변수 증가시켜줌
		return;
	}

	for (int c = 0; c < N; c++) {
		if (!chk(r, c)) continue;
		flag_col[c] = 1;				// 해당 열 방문처리
		flag_LD[r - c + (N - 1)] = 1;			// 해당 좌표로부터 왼쪽 위 방문처리
		flag_RD[r + c] = 1;				// 해당 좌표로부터 오른쪽 위 방문처리
		DFS(r + 1);
		flag_col[c] = 0;				// 다른 경우의 수 탐색하기 위해 플래그 배열 모두 초기화
		flag_LD[r - c + (N - 1)] = 0;
		flag_RD[r + c] = 0;
	}
}


int main()
{
	scanf("%d", &N);
	DFS(0);				// 0번째 행부터 탐색을 시작한다. 
	printf("%d\n", cnt);
	return 0;
}

먼저 N * N 행렬에 N개의 퀸을 위치시키려면 각 행에 무조건 1개씩 놓아야 한다. 

따라서 각 행의 어떤 열에 퀸을 놓아줄지 탐색하기 위해 DFS의 인자로 "행의 번호(r)" 를 넘겨준다. 

 

나는 해당 문제의 코드를 수업에서 배웠지만, 아마도 처음 문제를 접하고 0부터 코드를 짜려고 한다면 가장 막히는 부분이 "flag_LD(왼쪽 대각선 위에 퀸이 있는지), flag_RD(오른쪽 대각선 위에 퀸이 있는지)를 어떻게 확인하는지"일 것이다. 

 

규칙을 찾아보면, 왼쪽 대각선에 있는 좌표들은 그 차이(r - c)가 같다. 이때 r - c + (N - 1)을 해주는 이유는, 맨 오른쪽 위부터 맨 왼쪽 아래까지 (r - c)의 종류가 2 * N - 1개 나오기 때문이다. 한편 오른쪽 대각선에 있는 좌표들은 그 합(r + c)이 같다. 이러한 규칙 때문에 이차원 배열이 아닌 일차원 배열로 플래그를 세우는 것이 가능하다.