[C++] 9663: N-Queen

풀이

1차원 배열을 이용하여 체스판을 표현한다
퀸은 한 행에 하나씩만 놓을 수 있으므로, N*N의 체스판에 N개의 퀸을 배치하려면 모든 행에 하나의 퀸이 배치되어야 한다!

정답코드

#include <iostream>
using namespace std;

#define MAX 15

int col[MAX];
int N, total = 0;

// 다른 퀸의 이동경로인지 체크
bool check(int level) {
	for (int i = 0; i < level; i++) {
		if (col[i] == col[level] || abs(col[level] - col[i]) == level - i)
			return false;
	}
	return true;
}

void nqueen(int level) {
	if (level == N) total++;
	else {
		for (int i = 0; i < N; i++) {
			col[level] = i;
			if (check(level)) nqueen(level + 1);
		}
	}
}

int main() {
	cin >> N;
	nqueen(0);
	cout << total;
}

오답코드

void dfs(int x, int y) {

	// 퀸 놓기
	visit[x][y] = true;
	cnt++;
	if (cnt == N) {
		ans++;
		return;
	}

	// 퀸의 이동경로 막기
	for (int i = 1; i <= N; i++) {
		if (x + i <= N) visit[x + i][y] = true;
		if (y + i <= N) visit[x][y + i] = true;
		if (x - i >= 0) visit[x - i][y] = true;
		if (y - i >= 0) visit[x][y - i] = true;
		if (x + i <= N && y + i <= N) visit[x + i][y + i] = true;
		if (x - i >= 0 && y - i >= 0) visit[x - i][y - i] = true;
		if (x + i <= N && y - i >= 0) visit[x + i][y - i] = true;
		if (x - i >= 0 && y + i <= N) visit[x - i][y + i] = true;
	}


	// 다음 퀸을 놓을 자리 탐색
	for (int i = x; i <= N; i++) {
		for (int j = y; j <= N; j++) {
			if (visit[i][j] == false) dfs(i, j);
		}
	}

	// 초기화
	visit[x][y] = false;


}

느낀 점

2차원 배열을 만들고, visit 배열을 이용해 퀸의 이동경로를 무식하게 막으려고 했다 😣
점점 코드는 복잡해지고 답이랑은 멀어져서 결국 답을 보고 공부했다...
이제 무지성 구현으로는 안되고 어떻게 하면 효율적으로 코드를 짤 수 있을지 고민해야 하는 시기가 온 거 같다
그리고 재귀랑 백트래킹은 해도해도 머리 아프다 하
당분간 재귀 문제 위주로 풀면서 감 좀 익혀야지 ㅠ_ㅠ