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

문제 링크

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

풀이

• N-Queen 문제는, 크기가 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없도록 놓는 경우의 수를 구하는 문제이다.
• 퀸이 서로 공격할 수 없는 조건은 다음과 같다.
  • 퀸이 놓였을 때 퀸 자신을 기준으로 일직선상(가로 및 세로)과 대각선 방향에는 아무것도 놓여있으면 안 된다.
• N-Queen 문제는 백트래킹의 가장 대표적인 예제로서, 퀸의 특성상 체스판 한 행당 한 개의 퀸만 존재할 수 있다는 것을 전제로 깔아두고 시작하는 것이 좋다.
• 또한, 이 문제는 N*N짜리 배열을 직접 만들 필요 없이, 크기가 N인 일차원 배열을 만든 후, 각 행의 몇 번째 열에 퀸이 있는지를 저장하는 방식으로 풀 수 있다.
  • 예를 들어 N = 4일때, 일차원 배열 row [] 에 아래와 같이 저장하면 된다.
    • row[0] = 2
      • 0행 2열에 퀸 존재
    • row[1] = 0
      • 1행 0열에 퀸 존재
    • row[2] = 3
      • 2행 3열에 퀸 존재
    • row[3] = 1
      • 3행 1열에 퀸 존재
• 한 행마다 하나의 퀸을 배치해가면서, 총 배치 행수가 N(N개의 퀸을 전부 배치)개가 되면, 경우의 수를 1개씩 늘려주는 방식으로 백트래킹을 진행할 수 있다.
• 따라서, 재귀함수의 매개변수에는 현재 몇 번째 행을 채우고 있는지를 기록하는 인자가 필요하다.
• 퀸을 배치해가면서 체크해야하는것은, "임의로 배치한 퀸이 다른 퀸과 같은 행 또는 같은 열에 있는가" 또는 "대각선에 위치해있는가"이다.
  • 기본적으로 대각선에 존재하는 좌표일 경우, (X, Y)의 대각선에 위치한 좌표 (A, B)는 반드시 X-A = Y-B를 만족한다.
    • 예를 들어 (0 , 1)을 기준으로 했을때,
    • 대각선에 있는 점 (1, 2) 은 (0 - 1) = (1 - 2) = -1 을 만족하며
    • 대각선에 있는 점 (2, 3) 은 (0 - 2) = (1 - 3) = -2 를 만족한다.
• 따라서, 우리가 정의한 1차원 배열의 정의에 따라서, X좌표와 Y좌표의 차이가 일정한 값을 가질 경우 해당 퀸과 대각선에 있다고 판단할 수 있다.

코드

#include <stdio.h>
#include <stdlib.h>
#define MAX 14
using namespace std;

// 입력
int n;

// 찾은 경우의 수 
int cnt = 0;

// queen의 위치를 저장할 배열의 길이를 maximum 으로 정적 할당
int queen_loc[MAX];

// 해당 행, 열 위치가 퀸의 위치로 가능한지 확인
int possible_loc(int row){

    // 입력 받은 행까지 탐색하며
    // 이전에 찾은 퀸들의 열 위치와 같은 열에 위치해 있거나, 대각선에 위치해 있다면 불가능하다고 판단
    for(int i=0; i<row; ++i){
        if ((queen_loc[i] == queen_loc[row]) || ( row - i == (abs(queen_loc[row] - queen_loc[i])))){
            return 0;
        }
    }
    return 1;
}

// nqueen 알고리즘 수행하며, 찾은 경우의 수 덧셈
void nqueen(int row){

    // n번째 행까지 n개의 퀸을 놓는 하나의 경우의 수를 찾았다면, 함수 종료
    if (row == n){
        cnt++;
        return;
    }
    // 모든 경우의 수를 찾지 못한 경우
    else{

        // 현재 행에서 모든 열 검사
        for (int col=0; col<n; ++col){       

            // 행 위치에 열 값을 할당
            queen_loc[row] = col;

            // 현재 행, 열 위치가 퀸의 위치로 문제 없다면, 다음 행 검사
            if (possible_loc(row)){
                nqueen(row + 1);
            }
            // 현재 행, 열 위치가 퀸의 위치로 문제가 있다면, 이어서 반복문 진행
        }
    }
}

int main(void){

    // 입력
    scanf("%d", &n);

    // nqueen 알고리즘 수행 (0번째 행부터 탐색)
    nqueen(0);

    // nqueen 알고리즘 수행 후, 찾은 경우의 수 반환
    printf("%d", cnt);

    return 0;

}

참고

• https://cryptosalamander.tistory.com/58