9663번 - N-Queen

📌문제

👉 문제보기

코드

#include <iostream>
#define MAX_SIZE 16

using namespace std;

int arr[MAX_SIZE];
int n, ans = 0;

bool check(int count) {
	// 이전까지 놓았던 모든 퀸들과 체크
    for (int i = 0; i < count; i++) {
        if (arr[i] == arr[count] || abs(arr[count] - arr[i]) == count - i) {	
            // 같은 줄이거나 대각선에 있는지 확인
            return false;
        }
    }
    return true;
}

void nqueen(int x) {
    if (x == n) {
    	// 퀸을 모두 놓았으면 증가
        ans++;
        return;
    }
    for (int i = 0; i < n; i++) {
        arr[x] = i;
        if (check(x)) {
            nqueen(x + 1);
        }
    }
}

int main() {
    cin >> n;

    nqueen(0);

    cout << ans;

    return 0;
}

🍳문제 풀이

이전에 놓았던 퀸의 배치가 같은 줄이거나 대각선상에 있으면 안되는 것을 체크해야 한다.
대각선에 있으면 |x1 - x2| == |y1 - y2|를 만족한다
1차원 배열로 퀸의 위치를 저장하여 판단

1. 임의의 자리에 퀸 놓기
2. 같은 줄이나 대각선에 퀸이 있으면 취소
3. 같은 줄이나 대각선에 퀸이 없으면 다음 행으로 이동
4. 1 ~ 3 반복 후에 모든 줄에 퀸을 놓았으면 ans 증가
5. 이전 줄에서 놓을 수 있는 다른 위치로 이동. 1 ~ 3 반복

사진으로 알아보기

퀸의 위치를 저장할 1차원 배열로 나타내면 아래와 같다.

동작방식 하나씩 보기

퀸을 (0, 0)에 놓았다. check의 조건에 위배되지 않음. nqueen(0 + 1) 호출

check false므로 i증가

마찬가지로 i값 증가

check true 이므로 nqueen(1 + 1) 호출

같은 방법으로 x = 2일 때 i는 4가 될 때까지 for문 반복한 뒤 다음 nqueen(2 + 1)을 호출
x = 4일 때까지 같은 방식으로 진행

x == 5가 성립 됐으므로 함수 종료

---

백트레킹.
이전 호출로 되돌아감

새로 놓을 자리가 없고 반복문 끝났으니 nqueen(4) 함수 종료.

nqueen(1) 까지 되돌아감.
i = 3인 경우 check true이므로 n == 5가 될 때까지 재귀호출

이후 이 과정의 반복