N-Queen 문제는 재귀를 이용한 완전탐색 문제의 정석 중 하나이다.
ko.wikipedia.org/wiki/%EC%97%AC%EB%8D%9F_%ED%80%B8_%EB%AC%B8%EC%A0%9C
여덟 퀸 문제 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 8 퀸 문제는 8x8크기의 체스판에 퀸을 8개 배치하는 문제이다. 1848년 막스 베첼이 처음 제안하였다. 이 문제를 일반화하면 NxN 크기의 체스판에 퀸을 N개 배치하는
ko.wikipedia.org
위키피디아에도 항목이 있는 것은 글을 작성하면서 처음 알았는데. 어쨋든 대충 저런 문제이다.
각 퀸이 서로를 잡지 않으면서, 판에 최대한 많이 둘 수 있는 경우를 구하는 문제라는 것.
우리에게 정사각형 모양 체스판의 크기 N(1<=N<15)가 주어질 때,
어떻게 하면 퀸을 최대로 두는 경우의 수를 모두 구할 수 있을까?
읽으며 참고할 수 있도록, BOJ에 올라온 문제 링크를 공유한다.
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
1. 모든 경우를 탐색한다.
일단 이 문제에는 특정한 공식이 없다.
그냥 다 둬봐야 한다. 모든 경우를 다 해보고, 그 중 가능한 경우가 몇 개인지 세는 것이 솔루션이다.
그렇다면 모든 경우 라는 말은 무슨 뜻일까?
체스판의 각 칸에 우리는 퀸을 둘 수도 있고, 두지 않을 수도 있다.
그렇다면, 예를 들어 4*4짜리 칸이 존재한다면, 우리는 총 16개의 칸에 둔다/두지 않는다를 선택할 수 있는 것이다.
그 중 각각의 퀸이 서로를 잡지 않으며 퀸 4개를 둘 수 있는 경우가 생길 것이다.
(그 이상은, 한 줄에 두 개의 퀸이 들어가기 때문에 서로를 잡게 되어 불가능하다. 이 조건을 기억해두자.)
그러면 지금까지 나온 조건을 가지고, 제일 처음의 솔루션을 만들어 보자.
임의의 함수 func(int x, int y)가 존재한다고 한다.
이때, 함수의 내용은 다음과 같다.
void func(int x, int y) {
if(y >= n) { // 세로로 범위를 넘으면, 마지막까지 문제가 없었다는 뜻. 정답으로 추가.
register_solution();
return;
}
if(x >= n) x = 0, y++; //가로로 범위를 넘으면, 초기화하고 다음 줄로 넘겨준다.
unqueen(x, y) //체스판에 퀸을 두지 않는다.
func(x+1, y) //이대로 진행시켜 본다.
queen(x, y) //체스판에 퀸을 둔다.
if(check_board_error() == true) return; //만약 다른 퀸과 간섭하면 이전으로 돌아간다.
func(x+1, y); //이대로 진행시켜 본다.
unqueen(x, y) //이전으로 되돌리기 위해, 뒀던 퀸을 치워준다.
}* 코드는 의사코드이다.
일단, 모든 칸을 순서대로 순회한다. 이때, 재귀적으로 탐색을 해서 로직을 간결하게 만든다.
각 칸에서, 우리는 두 가지 경우를 시험해 본다.
1. 이 자리에 퀸을 두지 않고, 다음 칸으로 넘어간다.
2. 이 자리에 퀸을 두고, 다음 칸으로 넘어간다.
단, 이 자리에 퀸을 뒀을때 다른 퀸이 이 퀸을 잡을 수 있다면, 이 동작을 무효로 하고 이전으로 돌아간다.
이 로직은, 분명히 답을 구할 수 있다. 그러나 문제가 존재한다.
너무 많은 연산이 필요하다!!
위의 경우, 판의 크기가 4인 만큼 16개의 칸을 검사해야 하는데,
각각의 칸은 둔다/두지 않는다 두 가지 선택이 가능하므로 단순히 생각하면 2^16 -> 65536 번의 연산이 필요하다.
물론 check_board_error라는 메서드를 통해 검증되지 않은 경우는 더 진행시키지 않지만,
그렇게 경우의 수가 줄어도 수만번의 연산이 필요하다는 이야기이다.
게다 check_board_error라는 메서드는 각 칸에 대해 가로, 세로, 양 대각선을 검사하므로
시간 복잡도가 적지 않을 것이다.
그러면 판의 크기가 n이라고 하면, 우리는 O(2^(N*N) * N) 만큼의 연산을 수행해야 한다는 이야기이다.
지금부터 이 솔루션을 한 단계씩 최적화해 보자.
2. 가로는 간단하게
위의 문제 해설에, 내가 이런 말을 써뒀다.
|
(N=4일때) 그 중 각각의 퀸이 서로를 잡지 않으며 퀸 4개를 둘 수 있는 경우가 생길 것이다. (그 이상은, 한 줄에 두 개의 퀸이 들어가기 때문에 서로를 잡게 되어 불가능하다.) |
퀸은 4방향과 대각선으로 움직일 수 있다. 그렇기 때문에, 두 개의 퀸이 서로를 잡지 않으려면
각각의 퀸은 다른 행에 있어야 한다.
더 쉽게 말하자면, 위의 경우에서 특정 위치에 퀸을 둔 경우, 같은 줄에는 다른 퀸을 두면 안된다!
즉 퀸을 두고, 바로 다음 줄로 점프해도 아무 문제가 없다는 뜻이다.
그렇다면 코드를 한번 수정해보자.
void func(int x, int y) {
if(y >= n) { // 세로로 범위를 넘으면, 마지막까지 문제가 없었다는 뜻. 정답으로 추가.
register_solution();
return;
}
if(x >= n) x = 0, y++; //가로로 범위를 넘으면, 초기화하고 다음 줄로 넘겨준다.
unqueen(x, y) //체스판에 퀸을 두지 않는다.
func(x+1, y) //이대로 진행시켜 본다.
queen(x, y) //체스판에 퀸을 둔다.
if(check_board_error() == true) return; //만약 다른 퀸과 간섭하면 이전으로 돌아간다.
func(0, y+1); //다음 줄로 개행시키고, x는 맨 앞으로 옮겨준다.
unqueen(x, y);
}이렇게 되면, 이전보다 확인해야 하는 경우의 수가 압도적으로 줄어든다.
하지만 이 코드에도 문제가 있다. 재귀를 너무 많이 호출하는데,
함수 호출 비용은 무시하기 어려울 정도의 비용이므로 이를 좀 더 줄여보고 싶다.
이 때 하나의 발상이 더 필요하다.
생각해보니 한 줄에 하나만 둘 수 있는데, 함수를 줄 단위로 움직이면 안되나?
즉, 각각의 함수가 줄을 순회하면서 하나의 칸을 선택하고, 그 칸에 퀸을 둔 뒤에 다음 줄로 이동한다는 뜻이다.
이해하기 쉽게 코드로 보자.
void func(int y) {
if(y >= n) { // 세로로 범위를 넘으면, 마지막까지 문제가 없었다는 뜻. 정답으로 추가.
register_solution();
return;
}
for(int x = 0; x < n; x++ ){ //어느 칸에 둘 지 순회하면서 본다.
if(check_board_error(x, y) == true) continue; // 이 칸에 둘 수 없으면 다음으로 넘긴다.
queen(x, y) //이 칸에 퀸을 둔다.
func(y+1); //다음 줄로 넘어간다.
}
}로직이 훨씬 간단해졌다!!
각 줄마다 반복문을 돌리면서 어느 칸에 퀸을 둘지 결정하고,
이미 다른 퀸이 있어서 부딫히는 자리라면 피한다.
그렇지 않다면, 그 자리에 둬보고 다음 줄로 넘긴다.
이렇게만 짜도, 조금의 최적화가 더해지면 위의 문제를 통과시킬 수 있다.
하지만, 우리는 여기서 더 최적화를 해보고 싶다.
3. 세로도 간단하게
함수의 흐름은 꽤 최적화를 잘 한 것 같은데, 문제는 check_board_error 부분이다.
저 부분에서 우리가 검사해야 할 것은 다음과 같다.
- 나와 같은 x좌표에 다른 퀸이 있는지
- 나와 같은 아래방향으로 가는 대각선에 다른 퀸이 있는지
- 나와 같은 위쪽방향으로 가는 대각선에 다른 퀸이 있는지
(나와 같은 y좌표는 검사할 필요가 없다. 앞서 구조를 개선했기 때문에.)
그런데, 실제로 저 내용을 검사하는 로직을 어떻게 짜야할지 생각을 해보자.
제일 단순한 방법은, 반복문을 돌려서 한칸씩 조회해보는 것이다.
나와 같은 x좌표에 있는지는 맨 윗줄부터 한줄씩 내려오면서 검사해보면 되고,
대각선은 내 좌표에서 x,y를 더하고 빼는 반복문을 구현하면 어떻게든 될 것이다.
대강 이런 느낌이라고 생각하면 되겠다.
boolean check_board_error(int x, int y) {
for(int i=0;i<y;i++) { //x좌표가 같은 칸 검사
if(board[i][x] == queen) {
return false;
}
}
for(int i=0;i<n;i++) { //우측 아래로 가는 대각선 검사
if(board[y+i][x+i] == queen) {
return false;
}
}
(나머지 대각선도 검사...)
}위와 같이 반복문이 쭉 쌓이게 된다!!
이제 이 중에서, x좌표가 같은 칸을 쉽게 검사하는 법을 생각해보자.
C나 C++로 알고리즘을 풀다 보면, 배열을 맵처럼 사용하는 경우가 많다.
변수를 만들어 저장해도 되지만, 값이 많고 유동적인 경우가 생기기 때문이다.
다음 예시를 한 번 보자.
//1부터 10 사이의 수를 5개 입력받는다.
//이후, 입력받은 수가 무엇인지 순서대로 출력한다.
void solution() {
int check_number[10] = {,}; //10개의 칸을 0으로 초기화
for(int i=0;i<5;i++) {
int number = INPUT(); //입력을 받는다.
check_number[number] += 1;
}
for(int i=1;i<=10;i++) {
printf(i + "번째 숫자는 " + check_number[i] + "번 입력되었습니다.\n");
}
}위에서 보면, 어떤 수가 들어왔을 때 그 수를 번지로 하여 배열의 특정 칸에 기록을 남겨주는 것을 볼 수 있다.
물론 int one, two....ten 까지 여러 개의 변수를 만들수도 있지만,
그러면 코드도 더려워지고 대응하는 로직을 짜기도 어려우니까,
저렇게 내 값에 맞는 칸에 값을 저장하는 것이다.
Java나 python을 해보신 분이라면, map이나 dictionary 등의 이름으로 익숙하게 쓰고 있을 것이다.
C++도 STL로 관련 기능을 지원하지만, 이런 간단한 연산을 할 때엔 배열을 쓰는게 편하고 빠르다.
다시 돌아와서, 이런 가정을 해보자.
우리가 check_number라는 배열을 만들고,
퀸을 둘 때마다 그 퀸의 위치를 거기 저장한다고 해보자.
그러면 우리가 퀸을 두기 전에, 그 배열의 해당 칸을 보고 이미 뒀는지 판단할 수 있지 않을까?
바로 코드로 옮겨보자.
void func(int y) {
if(y >= n) { // 세로로 범위를 넘으면, 마지막까지 문제가 없었다는 뜻. 정답으로 추가.
register_solution();
return;
}
for(int x = 0; x < n; x++ ){ //어느 칸에 둘 지 순회하면서 본다.
if(check_number[x] == true) continue; //이미 같은 x좌표에 퀸이 있으면 다음칸으로
if(check_cross_error(x, y) == true) continue; // 대각선을 검사해서 둘 수 없으면 다음칸으로
queen(x, y) //이 칸에 퀸을 둔다.
check_number[x] = true; //x좌표 배열에 표시해준다.
func(y+1); //다음 줄로 넘어간다.
check_number[x] = false;//바뀐 값을 복원해줌
}
}코드가 엄청 간단해졌다!!
이렇게 하면 같은 x좌표에 있는 퀸을 검사하는 데에 시간복잡도를 많이 안쓸 것이 예상된다.
하지만 아직도 최적화 욕심이 난다.
4. 대각선까지 간단하게
앞서의 과정을 통해, 우리는 가로/세로로 퀸이 겹치는지 손쉽게 검사할 수 있게 되었다.
그러나, 아직도 대각선 검사는 로직이 복잡하다.
반복문을 돌려서 직접 순회해 봐야하는데, 이게 매 칸마다 해줘야 하니 시간복잡도에 생각보다 영향을 많이 준다.
여기서, 혹시 x좌표 검사할 때 사용했던 배열 매핑 방식을 대각선에도 할 수 있는지 궁금해진다.
혹시 가능할까? 당연히 가능하다.
자, 위 그림에 3*3짜리 체스판이 주어진다.
각 칸에는 x,y좌표를 표시해 줬다. 이 때, 같은 대각선에 있는 칸들은 어떤 규칙을 가질까?
|
우측 위로 가는 대각선은, x,y의 합이 서로 같다. (0,2와 1,1은 같은 대각선에 있다) 우측 아래로 가는 대각선은, x,y의 차가 서로 같다. (1,0과 2,1은 같은 대각선에 있다) |
그렇다. x+y와 x-y가 같다는 것. 이것이 같은 대각선 칸의 규칙이다.
그러면 앞서 만든 것처럼 check_cross_up과 check_cross_down 배열을 만들어서 매핑하면 되겠네?
다만 x-y는 음수가 될 수 있으니, 배열에 매핑할 경우 보정값이 필요하다.
x-y는 -n보다 작아질 수 없으므로, n을 보정값으로 더해주면 해결. 코드로 보자.
void func(int y) {
if(y >= n) { // 세로로 범위를 넘으면, 마지막까지 문제가 없었다는 뜻. 정답으로 추가.
register_solution();
return;
}
for(int x = 0; x < n; x++ ){ //어느 칸에 둘 지 순회하면서 본다.
if(check_number[x] == true) continue; //가로로 같은칸 검사
if(check_cross_up[x+y] == true) continue; // 위로가는 대각선을 검사
if(check_cross_down[x-y+n] == true) continue; // 아래로가는 대각선을 검사
queen(x, y) //이 칸에 퀸을 둔다.
check_number[x] = true; //x좌표 배열에 표시해준다.
func(y+1); //다음 줄로 넘어간다.
check_number[x] = false;//바뀐 값을 복원해줌
}
}앞서 check_board_error라는 메서드로 표현했던 복잡한 검사 로직이,
이제 간단한 if문으로 축소되었다.
이를 통해 우리는 엄청난 시간 효율을 얻을 수 있다.
5. 최종 코드
위의 단계를 하나씩 밟아나갔다면, 당신도 이 문제를 간결하게 풀 준비가 되었으리라 믿는다.
여기에 BOJ 통과 코드를 첨부한다. 꼭 위의 과정을 거친 뒤 이 코드를 봐주시길.
C++로 작성하였으나 옛날 C 코드나 다름없는 코드이다.
#include<stdio.h>
bool check_sum[300],check_diff[300],check_x[300];
int n,cnt;
void solution(int y){
if(y >= n){//끝까지 순회한 경우...
cnt++;
return;
}
//------------
for(int x=0;x<n;x++){
if(check_x[x] || check_diff[n+x-y] || check_sum[x+y])
continue;
check_diff[n+x-y]=true;
check_sum[x+y]=true;
check_x[x]=true;
solution(y+1);
check_diff[n+x-y]=false;
check_sum[x+y]=false;
check_x[x]=false;
}
}
int main(){
scanf("%d",&n);
solution(0);
printf("%d\n",cnt);
return 0;
}통과에 걸리는 시간은 1600ms 전후.
아마 대각선 처리를 해주지 않고 반복문을 좀 돌려도 10000ms 내로 통과가 가능할 것이다.
잘못된 부분이 있다면 지적 부탁드립니다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| cin과 out의 시간 단축을 위한 몇 가지 팁 (0) | 2021.08.14 |
|---|
댓글