[백준/BOJ] 9663번: N-Queen

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

9663번: N-Queen

 

 

---

 

 

문제

---

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

---

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

 

출력

---

 

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

 

예제 입력

---

8

 

예제 출력

---

92

 

코드 

---

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

int n, cnt;
vector<int> v;
void dfs(int row) {
	//n - 1번 행까지 탐색했다면 리턴
	if (row == n) {
		cnt++;
		return;
	}
	// row번 행의 i번째 위치에 퀸을 놓아 봄
	for (int i = 0; i < n; i++) {
		// row번 이전 행들을 탐색
		// 현재 위치의 퀸이 이전 위치의 퀸들과 
		// 세로, 대각선 방향에 위치한다면 퀸을 다음 위치로 옮겨서 놓아 봄
		//그렇지 않다면 해당 위치에 퀸을 놓을 수 있다는 것이므로 다음 행 탐색
		bool flag = true;
		for (int j = 0; j < row; j++) {
			if (i == v[j] || row - j == abs(i - v[j])) {
				flag = false;
				break;
			}
		}
		if (!flag) continue;
		v[row] = i;
		dfs(row + 1);
		v[row] = -1;
	}
}

void n_queen(int num) {
	for (int i = 0; i < num; i++) {
		//0번 행의 i번째 위치에 퀸을 놓고 시작할 때
		v[0] = i;
		dfs(1);
	}
	cout << cnt;
}

int main() {
	cin >> n;
	v.assign(n, -1);

	n_queen(n);
	return 0;
}

 

 

 

---

 

 

대각선 방향은 어떻게 따질 것인지가 고민이었는데 사실 별거 아니어따.. 검색하기 전에 손으로 몇번 끄적끄적 해볼걸..

그 다음 고민은 N x N의 체스판을 어떻게 표현할것인가 였다.

N이 작은 값이기 때문에 충분히 2차원 배열을 할당할 수 있었지만 for문을 많이 중첩해서 사용할 것 같아 2차원 배열은 사용하면 안될 것 같았다. 

이 부분도 검색...

검색해보니 대부분 1차원 배열에 인덱스는 row, 값은 column을 저장하여 구현하는 것 같았다. 새로운 방법을 터득함..!

여기까지만 검색을 통해 해결했고 그 다음은 dfs로 백트래킹을 적절히 구현하여 해결했다.(주석 참고)

 

전체적인 과정은 다음과 같다.

1. row 번 행에는 퀸을 하나만 놓을 수 있다.
2. row 번 행의 i 번 열에 퀸을 배치했다고 가정한다.
3. 0 ~ row-1 번 행에 위치하는 퀸들이 row번 행의 퀸과 세로 방향, 대각선 방향으로 겹치는 곳에 하나라도 위치한다면, row번 행의 i 번 열에는 퀸을 놓을 수 없는 것이다. 따라서 다음 열을 탐색한다.
4. 0 ~ row-1 번 행에 위치하는 모든 퀸들이 row번 행의 퀸과 세로 방향, 대각선 방향으로 겹치지 않는다면, row번 행의 i 번 열에는 퀸을 놓고 다음 행을 탐색한다.
5. 체스판의 마지막 행까지 모두 탐색했다면 해당 경로는 문제의 조건에 맞게 퀸을 배치할 수 있는 경로이다. 따라서 카운트 값을 1 증가시킨다.