3주차(백트래킹) - [C++]백준9663 N-Queen

18 Mar 2022 in Study on Algorithm

백준9663 N-Queen 링크

문제

예제 입력

---

코드

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

vector<int> arr1; // 세로
vector<int> arr2; // 대각선1
vector<int> arr3; // 대각선2
int cnt = 0;
int n;

void N_Queen(int row) {

	if (row == n) {
		cnt++;
		return;
	}

	for (int i = 0; i < n; i++) {
		if (arr1[i] == 0 && arr2[row + i] == 0 && arr3[n - 1 + row - i] == 0) {
			arr1[i] = 1; arr2[row + i] = 1; arr3[n - 1 + row - i] = 1;
			N_Queen(row + 1);
			// 완성이 아니여서 되돌림
			arr1[i] = 0; arr2[row + i] = 0; arr3[n - 1 + row - i] = 0;
		}
	}
}

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

	cin >> n;
	// 세로
	for (int i = 0; i < n; i++) {
		arr1.push_back(0);
	}
	// 대각선
	for (int i = 0; i < 2 * n - 1; i++) {
		arr2.push_back(0);
		arr3.push_back(0);
	}
	// 가로기준으로 확인
	N_Queen(0);
	cout << cnt;
}

설명

이 문제는 정해진 N x N 체스판에서 N개의 퀸으로 서로 잡지 못하는 상황을 만든다면 카운트해줍니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 가로, 세로, 대각선을 확인하는데 이미 현재 상태로 원하는 상태가 만들어지지 않을때 거기서 계속 이어가지 않고 다른 상태로 넘어갑니다.

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과