백준 9663 N-Queen (C++)

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

9663번: N-Queen

 

문제!

---

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

---

문제는 되게 간단하다!

테이블에 N개의 퀸이 놓여지는가에 대한 답을 출력하면 되는!

 

하지만.... 단순 탐색이라 생각했던 저는 되게 코드가 꼬여 버렸네요....

하나 놓으면서 공격당했는지도 봐야하고... 공격범위에 안놓도록 표시하고, 중복 처리도 해줘야하고...

#include <iostream>

using namespace std;

int table[16][16] = { 0 };// 놓을수있는지
int visit[16][16] = { 0 }; // 놓았었는지 더이상 사용 x 중복

int location[16][16] = { 0 };

int n = 0;
int answer = 0;
bool attack = false;

int dy[] = { 1,0,-1,1,0,-1,-1,1 };// 왼쪽 ,오른쪽 , 위 아래
int dx[] = { -1,-1,-1,1,1,1,0,0 };


void check(int y,int x) {
    int count;
    table[x][y] = 0;
    for (int i = 0; i < 8;i++) {
        count = 1;
        while ((y + dy[i]* count >= 0 and y + dy[i]* count < n) and (x + dx[i]* count >= 0 and x + dx[i]* count < n)) {
            if (location[y + dy[i] * count][x + dx[i] * count] == 1) {
                attack = true;
            }
            else {
                table[y + dy[i] * count][x + dx[i] * count] = 0;
            }
            

            count += 1;
        }
    }
}

void uncheck(int y, int x) {
    int count;
    table[x][y] = 1;
    for (int i = 0; i < 8; i++) {
        count = 1;
        while ((y + dy[i] * count >= 0 and y + dy[i] * count < n) and (x + dx[i] * count >= 0 and x + dx[i] * count < n)) {
            table[y + dy[i] * count][x + dx[i] * count] = 1;
            
            count += 1;
        }
    }
}



void dfs(int count) {
    
    if (count == n) {
        answer += 1;
        return;
    }

    for (int i = 0; i < n;i++) {
        for (int j = 0; j < n; j++) {
            if (table[i][j] == 1 and visit[i][j]==0) {
                location[i][j] = 1;
                check(i, j);
                
                if (!attack) {
                    dfs(count + 1);
                }
                else {
                    attack = false;
                }
                uncheck(i, j);
                location[i][j] = 0;
                visit[i][j] = 1;
            }

        }
    }


    
}


int main() {
    

    cin >> n;

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

    dfs(0);
    

    cout << answer << endl;
}

 

결국 포기....

 

 

다른 방법으로 해보기로 했습니다.

 

 

체스판을 생각해보면

 

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

 

이런식으로 있고

 

퀸을 배치해보면

1 0 0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0

....... 이런식으로 한 행에 하나씩, 한 열에 하나씩 배치되게 됩니다.

 

이 방법을 통해서 한 행에 어디에 위치하는지만 체크해주고 각 행에 하나씩 넣어주면? 

 

저처럼 모든 방향에 대한 재귀가 아닌 좀 더 간단한 방법으로 구현 가능합니다!

 

 

시작!

 

일단 행당 표시할 배열을 하나 만들어 주고

int table[15];
int N, answer = 0;

 

 

탐색부분을 만들어 아래처럼 재귀로 구현했습니다.

void find(int x)// 탐색부분
{
    if (x == N) {
        answer++;
    }
    else{
        for (int i = 0; i < N; i++){
            table[x] = i;// 체스판 한줄에는 퀸이 하나씩 배치되므로 일차원 배열로 퀸의 위치를 파악해준다.
            if (check(x)) {// 대각선에 퀸이 있는지만 파악해준뒤 바로 재귀!
                find(x + 1);
            }
        }
    }
}

 

그 다음은 현재 선택한 칸에 대해 같은 열에 퀸이 없는지, 앞뒤 대각선 위치에 퀸이 있는지를 판별해 구현해주는 방법!

bool check(int level){
    for (int i = 0; i < level; i++) {
        if (table[i] == table[level] || abs(table[level] - table[i]) == level - i) {// 같은 열에 있는지, 앞뒤 대각선 방향에 있는지
            return false;
        }
    }
    return true;
}

 

대각선은 또 일일히 보고있었는데 아래 블로그에서 신박한 방법을 알려주시네요!

 

[백준 / BOJ] - 9663번 N-Queen C++ 풀이

 

이렇게 탐색을 통해 답을 구해주면 끝!

 

 

ALL

#include <iostream>

using namespace std;

int table[15];
int N, answer = 0;

bool check(int level){
    for (int i = 0; i < level; i++) {
        if (table[i] == table[level] || abs(table[level] - table[i]) == level - i) {// 같은 열에 있는지, 앞뒤 대각선 방향에 있는지
            return false;
        }
    }
    return true;
}

void find(int x)// 탐색부분
{
    if (x == N) {
        answer++;
    }
    else{
        for (int i = 0; i < N; i++){
            table[x] = i;// 체스판 한줄에는 퀸이 하나씩 배치되므로 일차원 배열로 퀸의 위치를 파악해준다.
            if (check(x)) {// 대각선에 퀸이 있는지만 파악해준뒤 바로 재귀!
                find(x + 1);
            }
        }
    }
}

int main() {
    cin >> N;
    find(0);

    cout << answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!