[9663] N-Queen - 백트랙킹 ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/9663

9663번: N-Queen

---

[ 문제 접근 ]

 

우선 유명한 N-Queen 문제이다. 

 

한번 풀어봤기 때문에 백트랙킹 문제라는것은 알고 있었는데, 구현하자니 조금 고민 됐던 문제였다.

 

처음 푼 코드와 시간이 지나고 다시 푼 코드를 비교 해보자.

---

[ 처음 코드 ]

 

사실 첫번째 코드는 내가 풀었다기 보다

강의를 보고 힌트를 얻은 다음에 푼거라 보고 풀었다고 생각한다.

 

#include<iostream>
#include<vector>
 
using std::cin; using std::cout;
 
int n, answer;
int cols[16];
 
bool promising(int level) {  // 대각선, 세로에 다른 퀸 없는지 검사.
	if (level == 1)return true;  // 첫번째 퀸은 어디든 가능.
	for (int i = level - 1; i >= 1; i--) { // 현재 레벨 전 퀸들 전부 검사.
		// 대각선 검사. ( 두 지점 가로 차이랑 = 세로 차이랑 같으면 대각선.
		if (std::abs(cols[level] - cols[i]) == (level - i)) {
			return false;
		} // 세로 검사.
		else if (cols[i] == cols[level]) {
			return false;
		}
	}
	return true;  // 전부 검사했는데도 false 안되면 true;
}
 
void nQueen(int level) {
	
	for (int i = 1; i <= n; i++) {
		cols[level] = i;
 
		if (promising(level)) { // cols[level]이 i가 될 수 있다면
			if (level == n) {
				answer++;
				return;
			}
			nQueen(level + 1);
		}
	}
 
}
 
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
 
	cin >> n;
	int level = 1;
	nQueen(level);
	cout << answer;
	return 0;
}

 

[ 복습 코드 ]

 

#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, cnt;
vector<pair<int,int>> buffer;
 
bool check(int col,int k) { // 대각선, 세로 겹치는지 체크.
	for (int i = 0; i < k; i++) {
		if (buffer[i].second == col) return false;
		if (std::abs((buffer[i].second - col) )== std::abs((buffer[i].first - k))) return false;
	}
	return true;
}
void nQueen(int k) {
 
	if (k == n) {
		cnt++; // 정답 증가
		return;
	}
	for (int i = 0; i < n; i++) {
		if (check(i,k)) {
			buffer[k].first = k;
			buffer[k].second = i;
			nQueen(k + 1);
		}
	}
	
}
 
int main() {
	
	cin >> n;
	buffer.resize(n);
	nQueen(0);
	cout << cnt;
 
	return 0;
}

---

[ Key Point ]

 

👉 백트랙킹 문제라는건 알고 있었고, 관건은 구현을 할 수 있느냐 없느냐.

 

 

---

[ 다른 사람 풀이 ]

 

ref :: https://cryptosalamander.tistory.com/58