[백준 && SW] gold5/D3 N-Queen

백준과 SW Expert Academy 양쪽에 있는 문제이다.

수업에서도 들었던 기억이 있다.

 

// 같은 행과 열에 하나씩 들어갈 수 있음
// 대각선인지만 확인하면됨. 같은 x좌표끼리의 차이와 y좌표끼리의 차이가 같으면 대각선에 존재
// 모든 행이 꽉찼으면 끝


#include<iostream>
#include<vector>

using namespace std;

int N, answer;
vector<int> chess(14); // 각 원소는 n번째 행의 어느 column에 chess가 놓여있는지를 나타내고있다.
vector<bool> columns(14, false);

void dfs(int row = 0) { // row번째 행에 넣을 차례
	if (row == N) {
		answer++;
		return;
	}
	for (int i = 0; i < N; i++) { // 어느 column에 넣을지
		// 같은 열에 없어야함
		if (columns[i]) continue;
		// 대각선에 없어야함
		bool conti = false;
		for (int j = 0; j < row; j++) { // row의 전 행들을 돌면서
			if (abs(row - j) == abs(i - chess[j])) conti = true;
		}
		if (conti) continue;
		chess[row] = i;
		columns[i] = true;
		dfs(row + 1);
		columns[i] = false;
	}
}

int main() {
    answer = 0;
    cin >> N;

    dfs();
    cout << answer << endl;
}

---

문제

백준

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

9663번: N-Queen

SW Expert Academy

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

728x90

---

[접근]

같은 행이나 열에 하나만 놓일수 있다는 것을 깨닫고 나면 쉽다.

따라서 나는 chess라는 vector를 n번째 행의 어느 column에 chess가 놓여있는지 입력하는 용도로 사용하였고,

column에도 하나씩만 들어갈 수 있기 때문에 이미 차지 되었는지 확인하기 위해 columns라는 boolean vector를 만들어 사용하였다.

14라고 쓴것은, chess판의 최대 크기가 14라고 주어졌기 때문이다.

int N, answer;
vector<int> chess(14); // 각 원소는 n번째 행의 어느 column에 chess가 놓여있는지를 나타내고있다.
vector<bool> columns(14, false);

dfs

https://jolly-note.tistory.com/62?category=993245 

DFS (Depth First Search, 깊이 우선 탐색)

---

[접근1] - dfs 함수 내부

모든 행을 다 채웠으면 answer를 1 증가시키고 끝난다.

column들을 돌면서, 어느 column에 넣을 지 확인하는데,

이미 해당 열에 놓여져있거나, 대각선에 놓여져있다면 continue한다.

대각선에 놓여있는것은 해당 위치에서 좌/우로 n번 상/하로 n번 이동한다는것을 의미, 즉, x 좌표끼리 뺀 값과 y 좌표끼리 뺀 값의 크기가 동일하면 대각선 위치에 있는것이다.

void dfs(int row = 0) { // row번째 행에 넣을 차례
	if (row == N) {
		answer++;
		return;
	}
	for (int i = 0; i < N; i++) { // 어느 column에 넣을지
		// 같은 열에 없어야함
		if (columns[i]) continue;
		// 대각선에 없어야함
		bool conti = false;
		for (int j = 0; j < row; j++) { // row의 전 행들을 돌면서
			if (abs(row - j) == abs(i - chess[j])) conti = true;
		}
        ...
	}
}

---

[접근2] - dfs 함수 내부

해당 위치에 놓을 수 있다면, 해당 row 위치에 chess에 i(column nb)를 대입하고, 해당 column이 찼다는것을 표시하기위해 columns[i]를 true로 바꿔준다.

이후 dfs로 다음 행을 진행하고, dfs를 마치고 돌아왔을 때, chess위의 말을 제거하는것과 동일하므로 해당 column을 false로 되돌려준다.

void dfs(int row = 0) { // row번째 행에 넣을 차례
	...
	for (int i = 0; i < N; i++) { // 어느 column에 넣을지
		...
		if (conti) continue;
		chess[row] = i;
		columns[i] = true;
		dfs(row + 1);
		columns[i] = false;
	}
}