[백준 9663 c++] N-Queen

문제 링크

www.acmicpc.net/problem/9663

9663번: N-Queen

 

문제 접근

// 접근: 2중 반복 완전탐색으로 퀸의 놓을 수 있는 위치 저장해 가며 놓기 -> 너무 오래걸릴듯

// 접근2: dfs를 이용하여 퀸의 경우를 조사하는데 백트래킹을 통해 경우의 수를 줄인다

 

 

 

 

 

 

 

 

 

 

문제 풀이

// 풀이: 놓는 퀸의 위치를 저장 후 백트래킹을 해서 경우의 수를 줄이고 dfs 이용

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

주의

 

 

 

 

개념

 

 

 

 

 

 

 

 

 

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>
#include <map> // map구조체
#include <numeric> //accumulate(v.begin(), v.end(), 0);

// [백준 9663 c++] N-Queen
// 접근: 2중 반복 완전탐색으로 퀸의 놓을 수 있는 위치 저장해 가며 놓기 -> 너무 오래걸릴듯
// 접근2: dfs를 이용하여 퀸의 경우를 조사하는데 백트래킹을 통해 경우의 수를 줄인다 
// 풀이: 놓는 퀸의 위치를 저장 후 백트래킹을 해서 경우의 수를 줄이고 dfs 이용

using namespace std; // cin,cout 편하게 사용 라이브러리
#define MAX 16

int n;
int rowloc[MAX] = { -1, }; // 퀸의 위치 배열
int colloc[MAX] = { -1, };
int result = 0;

void dfs(int row, int col)
{
	//백트래킹(가지치기)
	// 퀸의 위치가 안되면 백트래킹
	for (int i = 0; i < row; i++) // 현재 퀸의 개수만큼 검사
	{
		if (row == rowloc[i]) { return; } // 가로
		if (col == colloc[i]) { return; } // 세로
		if (abs(row - rowloc[i]) == abs(col- colloc[i])) { return; } // 대각선 검사

	}
	// 퀸의 위치 저장
	rowloc[row] = row;
	colloc[row] = col;
	if (row == n-1) { result++; return; }

	// 다음 행에서의 dfs
	for (int i = 0; i < n; i++)
	{
		dfs(row + 1, i);
	}
}

int main()
{
	// IO 속도 향상
	//ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	
	// 첫 퀸의 첫행에  놓는  경우
	for (int i = 0; i < n; i++)
	{
		dfs(0, i);
	}
	cout << result;
	return 0;
}