[BOJ] 백준 9663 N-Queen
링크
https://www.acmicpc.net/problem/9663
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
풀이
#include <iostream>
using namespace std;
bool isused1[40]; //해당 인덱스 열에 대해 사용 여부를 표시. 인덱스 [y]
bool isused2[40]; //좌측 하단과 우측 상단을 잇는 대각선에 대해 사용 표시 -> 인덱스[x + y]
bool isused3[40]; //좌측 상단과 우측 하단을 잇는 대각선에 대해 사용 표시 -> 인덱스[x-y+n-1]
int cnt, n;
void func(int cur) {
if (cur == n) { // func(n)이 호출되면 퀸 n개 놓는데 성공했다는 의미이니 cnt를 1증가시킨다.
cnt++;
return;
}
for (int y = 0; y < n; y++) { // cur이 x축을 의미하는구나
if (!isused1[y] && !isused2[cur+y] && !isused3[cur-y+n-1]) {
isused1[y] = true;
isused2[cur + y] = true;
isused3[cur - y + n - 1] = true;
func(cur + 1);
isused1[y] = false;
isused2[cur + y] = false;
isused3[cur - y + n - 1] = false;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
func(0);
cout << cnt;
}
설명
📌 기본적은 각 행에 퀸이 하나씩 두게 된다.
각 경우의 수에 대해 모두 방문하며 D행에 퀸을 놓았다면 퀸을 4개 놓는데 성공했다는 의미다.
기본틀 : func(0)을 호출해 0번째 행에 퀸을 놓고 func(1)을 호출하고 이렇게 진행하다가 func(n)이 호출되면 퀸 n개 놓는데 성공했다는 의미이니 cnt를 1증가시킨다.
👨🏻🏫 각 행에 퀸을 한개씩만 놓으니까 한 행에 퀸이 2개인지는 생각할 필요가 없는데 열과 대각선에 열과 대각선에 대해서는 생각을 해야된다.
-
같은 열에 대한 조건 : y좌표가 같으면 같은 열이다.
-
좌측 하단과 우측 상단을 잇는 대각선 : x+y가 같으면 같은 대각선에 위치해있다.
-
좌측 상단과 우측 하단을 잇는 대각선 : x-y가 같으면 같은 대각선에 위치해있다.
놓은 모든 퀸에 대해 대각선 혹은 열에서 만나는 것이 있는지를 확인하려고 한다면 그 과정에서 O(N)이 추가로 필요하게 되는데 각 대각선과 열의 점유 상태를 나타낼 isused 변수를 두면 시간이 절약된다. -
isused1은 열에 대응되는 값으로, (x,y)에 퀸이 있으면
isused1[y]
를 true로 만든다. -
좌측하단과 우측상단 대각선 :
isused2[x+y]
를 true로 만든다. -
좌측상단과 우측하단 대각선 :
isused2[x-y+n-1]
를 true로 만든다. -> 인덱스를 음수로 보내지 않게 하기 위해서 n-1를 추가했다.
Author And Source
이 문제에 관하여([BOJ] 백준 9663 N-Queen), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dnflrhkddyd/BOJ-백준-9663-N-Queen저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)