[알고리즘] 백준 9663번: N-Queen, Backtracking의 대표 문제

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

9663번: N-Queen

N-Queen 문제는 백트래킹 알고리즘의 대표 문제라고 할 만큼 백트래킹하면 N-Queen 문제를 사람들이 많이 떠올린다. 하지만, 백트래킹을 이제 막 배우고, 겨우 구현할 수 있는 시점이라면 백트래킹을 공부하는 데에 있어서 당장 이 문제를 추천하고 싶진 않다. 백트래킹을 대표하는 문제이기는 하되 접근성이 쉬운 문제는 아니기 때문이다.

 

처음에 접근할 때는 2차원 배열로 접근을 했다. goQueen이라는 함수를 선언하여 퀸이 어느 좌표에 있으면 퀸이 갈 수 있는 모든 좌표를 못 가게끔 하여 다음에 놓을 수 있는 퀸들의 여러 가지 경우의 수를 따지는 코드를 구현하려 했었다. 결론적으로는 구현에 실패했을뿐더러 많이 복잡한 코드가 되었다.

(2차원 배열로 접근했던 코드는 맨 아래에)

 

---

솔루션

2차원 배열로 답을 구하는 게 당연하고, 1차원 배열은 생각도 못 하고 있던 시점에서 2차원 배열로 간단하게 구현이 가능할까 싶어서 솔루션을 찾아보고 있었는데 모든 사람들이 1차원 배열을 사용하여 코드를 구현했었다.

(+참고 https://cryptosalamander.tistory.com/58)

 

일차원 배열을 선언하여 각 인덱스를 각 행으로 취급을 하여 백트래킹을 돌리는 게 핵심이다.

허나, 여기서 주의할 건 대각선까지 어떻게 따질 것이냐가 또 쉽지 않아서 또 다른 포인트가 될 거 같다.

[정답]

#include <iostream>
using namespace std;
#define MAX 15

int N;
int cnt = 0;
int arr[MAX];

bool judge(int level) {
	for (int i = 0; i < level; i++) {
		if (arr[i] == arr[level] || abs(arr[level] - arr[i]) == level - i) {
        //같은 열에 있는가? 혹은 대각선에 존재하는가?
			return false;
		}
	}

	return true;
}

void nQueen(int n) {
	if (n == N) {
		cnt++;
	}

	for (int i = 0; i < N; i++) {
		arr[n] = i;
		if (judge(n)) {
			nQueen(n + 1);
		}
	}
}

int main() {
	cin >> N;
	nQueen(0);
	cout << cnt;
	return 0;
}

---

2차원 배열을 사용하여 구현하는 것도 어느 정도 된 상태였지만 실패한 거라 시간이 난다면 다시 시도해보고 싶다. (시간 초과가 나더라도 내 로직이 맞는가 확인하고 싶어서)

[내가 짠 코드(실패)]

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

// 지금 문제: success 할 경우, Queen에 그대로 덮어져서
// 다음 재귀에서 Queen을 다 활용하지 못 하여 따지지 못 하는 경우가 생김

// temp로 해결하려 했으나 temp 또한 재귀가 일어나면서 temp에 데이터가 덮어짐

int n;
int temp[15][15];
int Queen[15][15]; // 퀸이 갈 수 있고, 현재 위치를 담은 배열
// 갈 수 없게 되면 1을 넣고, 갈 수 있으면 0 그대로
int result = 0;

typedef struct {
	int y, x;
} Direction;

Direction queenMove[8] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, 1},
	{-1, 1}, {1, -1} };

void saveTemp() { // temp에 현재 Queen 상태 저장
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			temp[i][j] = Queen[i][j];
		}
	}
}

void tempToQueen() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			Queen[i][j] = temp[i][j];
		}
	}
}

void printQueen() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << Queen[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}

void goQueen(int row, int col) {
	Queen[row][col] = 1;
	//cout << row << ' ' << col << '\n';
	for (int i = 0; i < 8; i++) {
		int dy = row + queenMove[i].y;
		int dx = col + queenMove[i].x;
		//int debugCnt = 1;
		while (dy <= n && dy >= 1 && dx >= 1 && dx <= n) {
			//cout << "while 순서 " << debugCnt << '\n';
			Queen[dy][dx] = 1;
			//cout << dy << ' ' << dx << '\n';
			dy += queenMove[i].y;
			dx += queenMove[i].x;
			//debugCnt++;
		}
	}
}

void backTracking(int cnt) {
	if (cnt == n) {
		cout << "Success" << '\n';
		result++;
		return;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (Queen[i][j] == 0) {
				saveTemp();
				goQueen(i, j);
				printQueen();
				backTracking(cnt + 1);
				tempToQueen();
			}
		}
	}
}

void queenReset() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			Queen[i][j] = 0;
		}
	}
}


int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if(Queen[i][j] == 0){
				saveTemp(); // 전부 다 0인 상태 저장
				goQueen(i, j);
				printQueen();
				backTracking(1);
				tempToQueen(); // 초기화
			}
		}
	}

	cout << result;
	return 0;
}