백준 9663번 N-Queen

문제 링크 : https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

문제

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

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

 

입력

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

 

출력

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

 

풀이

문제 풀이에 앞서 체스에서 퀸이 공격할 수 있는 범위를 설명하자면,

퀸은 체스에서 가장 좋은 말로서, 자신이 위치한 지점 (a, b)에서부터 a 행과 b열 그리고 모든 대각선 방향을 전부 공격할 수 있다.

따라서 체스판에 퀸을 놓을 때 어느 한 행에 퀸이 놓여있다면, 그 행에는 퀸을 절대 놓을 수 없다.

따라서 크기 N X N 체스판에 놓을 수 있는 퀸은 N개임을 알 수 있다.

 

추가로 체스판의 크기는 최대 15개이기 때문에 15*15 번을 모두 확인해도 시간이 흘러넘쳐서 이 문제는 재귀 함수를 사용하는 브루트 포스 알고리즘으로 풀 수 있게 된다.

 

여기까지는 금방 생각한다. 문제는 재귀호출을 어떤 식으로 할 것인가?인데,

• 우선 한 행 or 한 열을 잡고 n번 돌려서 각각의 열 or 행마다 퀸을 놓은 후
• 이후 퀸을 놓을 때마다 이 칸에 놓을 수 있느냐? 없느냐를 배열을 봐서 퀸이 있는지 확인한 후 boolean 값을 반환한다.
• 행이 n과 같아질 때 정답 + 1 씩 해준다.

나는 한 행을 잡고, 행을 +1 씩 해주면서 재귀 호출을 해주었다.

따라서, 퀸이 있는지 확인하기 위해선, 다음에 놓으려는 퀸의 위치가 그 전 행보다 높고, 그 열에는 퀸이 없어야 하며

왼쪽 위 대각선과 오른쪽 위 대각선에 이미 놓여있는 퀸이 있는지 확인해야 한다.

 

직접 check 함수를 짜긴 했는데, 너무 알아보기 힘들어서 백준 님 코드를 인용해서 올립니다. ㅠㅠ

 

소스 코드

#include <iostream>
#include <cstdbool>
#include <cstring>
using namespace std;
 
int ans;
int n;
bool a[15][15];
bool check(int row, int col) {
    for (int i = 0; i < n; i++) { //열을 위로 올리면서
        if (i == row) continue;
        if (a[i][col]) return false; //해당 열에 갈 수 없는 경우 false 리턴
    }
    // 왼쪽 위 대각선
    int x = row - 1;
    int y = col - 1;
    while (x >= 0 && y >= 0) {
        if (a[x][y] == true) {
            return false;
        }
        x -= 1;
        y -= 1;
    }
    // 오른쪽 위 대각선
    x = row - 1;
    y = col + 1;
    while (x >= 0 && y < n) {
        if (a[x][y] == true) {
            return false;
        }
        x -= 1;
        y += 1;
    }
    return true;
}
void queen(int row) {
    if (row == n) ans++;
    for (int col = 0; col < n; col++) { //해당 열 확인
        a[row][col] = true;
        if (check(row, col)) { //열이 비어있으면 다음 행으로 전진
            queen(row + 1);
        }
        a[row][col] = false; //백트래킹
    }
}
int main()
{
    scanf("%d", &n);
    queen(0);
    cout << ans;
    return 0;
}
 
 

추가 설명

재귀 함수 맨 밑에 백트래킹을 구현했는데, 백트래킹을 하면, boolean 배열을 계속 새로 만들어서 주고받는 것보다 훨씬 메모리 소요가 덜하다. 보통 백트래킹은 재귀 함수가 끝나고 뒤에 다시 초기화하는 것을 말하며,

위 코드에서는 43번째 줄 a [row][col] = false가 그에 해당한다.

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~