개요

백준 9663번: N-Queen

• 입력
  첫째 줄에 N이 주어진다. (1 ≤ N < 15)

• 출력
  첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

접근 방식

1. 퀸은 행과 열에 하나씩 존재해야한다는 조건에서 아이디어를 얻어
   각 행에 하나씩 퀸을 놔보는 경우를 백트래킹 방식으로 다 조사한다.

2. 퀸이 있는 위치를 저장하기위해 queen배열을 만들었다.

   //몇번째행에 퀸이 어디있는지 checkQueenCanPos에서 사용될 것
   int queen[15];

   n번째 행의 m번째 열에 퀸이 있다면

   queen[n]=m; 

   이런식이다.

3. 백트래킹으로 각 행의 0열부터 9열까지 퀸이 들어갈 수 있는지
   조사하는 함수 checkQueenCanPos()를 만들었다.

   퀸의 좌표와 조사하려는 좌표의 행과 열의 차이가 같다면 대각선에 존재한다.

   //h행 w열에 퀸이 들어갈 수 있는지 보는 것.
   bool checkQueenCanPos(int h,int w) {
   
   	for (int i = 0; i < h; i++) {
   		//같은 열에 존재하면 false
   		if (queen[i]==w) return false;
   		//대각선에 존재하면 false
   		if (abs(h - i) == abs(w - queen[i]))
   		return false;
   	}
   	return true;
   }

4. 백트래킹을 통해 한 행마다 퀸 하나씩 배치해주고,
   끝의 행까지 진행했다면 다시 돌아오며 마지막으로 배치한 퀸을 제거해준다.

   /// <summary>
   /// 열마다 하나 행마다 하나씩 배치해야하므로 각 열의 행에 넣었을 때 백트래킹
   /// </summary>
   /// <param name="h"></param>
   /// <param name="w"></param>
   /// <param name="amount"></param>
   void Backtracking(int h,int w,int amount) {
   	if (h == N) return;
   
   	for (int i = 0; i < N; i++) {
   		if (!checkQueenCanPos(h, i)) continue;
   		if (amount == N - 1) Ans++;
          //퀸 배치
   		queen[h] = i;
   		Backtracking(h+1,w, amount+1);
          //백트래킹의 한 단계가 끝나면 마지막 퀸 제거
   		queen[h] = 0;
   	}
   }
   

코드

#include<iostream>

using namespace std;
int N=0,Ans=0;
//몇번째행에 퀸이 어디있는지 checkQueenCanPos에서 사용될 것
int queen[15];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

void Input() {
	cin >> N;
}

//h행 w열에 퀸이 들어갈 수 있는지 보는 것.
bool checkQueenCanPos(int h,int w) {

	for (int i = 0; i < h; i++) {
		//같은 열에 존재하면 false
		if (queen[i]==w) return false;
		//대각선에 존재하면 false
		if (abs(h - i) == abs(w - queen[i]))
		return false;
	}
	return true;
}

/// <summary>
/// 열마다 하나 행마다 하나씩 배치해야하므로 각 열의 행에 넣었을 때 백트래킹
/// </summary>
/// <param name="h"></param>
/// <param name="w"></param>
/// <param name="amount"></param>
void Backtracking(int h,int w,int amount) {
	if (h == N) return;

	for (int i = 0; i < N; i++) {
		if (!checkQueenCanPos(h, i)) continue;
        //만약 퀸을 N개 배치했다면 정답 ++
		if (amount == N - 1) Ans++;
        //퀸 배치
		queen[h] = i;
		Backtracking(h+1,w, amount+1);
        //백트래킹 끝난 후 마지막 퀸 제거
		queen[h] = 0;
	}
}

void Solution() {
	Backtracking( 0,0, 0);
	cout << Ans;
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	Input();
	Solution();
}

문풀후생

유명한 백트래킹 문제다.
행에 하나씩 배치해야한다는 사실만 알면 실마리가 잡힌다.