[백준/BOJ] 9663번: N-Queen (백트래킹 기법) - C++ 문제 풀이

문제 설명

 

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

 

 

풀이

체스에서 퀸은 거리와 상관없이 직선, 대각선에 있는 적을 공격할 수 있는 말입니다.

이런 N개의 퀸을 N x N 크기의 체스판에 서로 공격할 수 없도록 배치할 수 있는 방법의 수를 찾는 문제입니다.

 

4x4 Queen 배치

 

위의 이미지는 4x4 체스판 위에 4개의 퀸들이 서로 공격할 수 없도록 배치된 예를 보여주고 있습니다.

이 문제는 백트래킹 기법의 전형적인 문제입니다.

 

백트리킹 기법이란 트리구조 문제의 정답을 찾는 과정에서, 더 이상 진행할 수 없는 노드에 도달하게 되면 이전 노드로 되돌아가 다른 방향으로 정답을 탐색하는 방법을 말합니다.

 

백트래킹 기법

 

 

위의 이미지를 대상으로 탐색 과정을 설명하면,

1번 노드부터 시작해서 2번 노드에 도달하여 정답이 될 수 있는 길이 맞는지 검사합니다.

정답이 될 수 있는 길이라면 깊이 우선 방법으로, 3번 노드를 검사하는 것이 아니라 계속해서 4번 노드로 진행합니다.

이러한 정답이 될 수 있는 2번 노드를 Promising Node라고 합니다.

 

4번 노드도 정답이 될 수 있는 길인지 검사합니다.

만약, 정답이 될 수 없는 길이라면 8번, 9번 노드는 검사할 필요가 없으므로 건너뜁니다.

이렇게 불필요한 노드들을 검사에서 제외하는 것을 가지치기(Pruning)라고 합니다.

 

그리고 다시 2번 노드로 돌아간 뒤, 5번 노드로 진행해 같은 방식으로 검사를 계속합니다.

 

이러한 백트래킹 기법을 이 문제에 적용해 보도록 합시다.

목표는 N개의 퀸을 서로 공격할 수 없도록 배치하고, 그 횟수를 기록하는 것입니다.

 

그 과정은 이렇게 진행될 것입니다.

우선 1번 말을 (1,1)의 위치에 두어봅니다.

두 번째 말을 다음 줄 (2,1) 위치에 두고, 정답이 될 수 있는지 검사합니다.

같은 열에 말이 있기 때문에 정답이 될 수 없습니다. 따라서, 세 번째와 네 번째 말은 둘 필요도 없습니다.

이렇게 세 번째, 네 번째 검사를 제외하는 것이 가지치기입니다. 

 

다시 1번 말을 둔 상태로 돌아가서,  두 번째 말을 (2,2) 위치에 두어봅니다.

그렇지만 이 위치도 정답이 될 수 없습니다.

대각선 상에서 두 말은 서로 공격할 수 있기 때문입니다.

 

그렇지만, 두 번째 말을 (2,3) 위치에 두면 1번 말과 서로 공격할 수 없으므로 정답이 될 가능성이 있습니다.

그럼 세 번째 줄에서 말의 위치를 찾기 위해 위와 같은 과정을 계속합니다.

 

이렇게 해서 N 번째 말까지 제대로 놓을 수 있다면 정답을 찾은 것입니다.

 

위의 과정을 코드로 바꾸면 아래와 같습니다.

row 번째 줄에 말을 놓고 검사를 수행해서 성공하면, 다음 줄에 말을 놓는 함수를 재귀적으로 호출합니다.

p [row] = i 식은 (row, i) 위치에 말을 놓았음을 의미합니다.

예를 들어, (2,1) 위치에 놓는 말을 p [2] = 1로 표현할 수 있습니다.

 

 

void N_queen(int row){
    
    if ( row == N){
        cnt++;  // N개의 퀸을 판에 놓았다. 정답 횟수를 기록한다
    }
    else{

        for(int i = 0; i < N; i++){
            
            p[row] = i;     // (row, i) 위치에 놓은 말
            
            if ( IsPromising(row)){ // 현재 줄에 말을 옮은 위치에 놓았으면

                N_queen(row+1); // 다음 줄에 말을 놓는다
            }
        }
    }
}

 

현재 놓은 말이 정답이 될 가능성이 있으려면(Promising), 이전의 말들과 같은 열 또는 대각선 상에 있으면 안 됩니다.

이 검사를 코드로 바꾸면 다음과 같습니다.

// row 열에 놓은 퀸과 이전 열의 퀸들 위치 비교
bool IsPromising(int row){
    
    for(int i = 0; i < row; i++){
        if ( (p[i] == p[row]) ||    // 같은 열
             ( abs( p[row] - p[i]) == row - i)) // 대각선 상에 위치
             return false;
    }

    return true;
}

 

 

소스 코드

#include <iostream>
using namespace std;

#define SIZE    14
int p[SIZE];    // 위치

int N;  // 체스판 사이즈
int cnt = 0;    // 서로 공격할 수 없도록 놓을 수 있는 횟수

// row 열에 놓은 퀸과 이전 열의 퀸들 위치 비교
bool IsPromising(int row){
    
    for(int i = 0; i < row; i++){
        if ( (p[i] == p[row]) ||    // 같은 열
             ( abs( p[row] - p[i]) == row - i)) // 대각선 상에 위치
             return false;
    }

    return true;
}

void N_queen(int row){
    
    if ( row == N){
        cnt++;  // N개의 퀸을 판에 놓았다
    }
    else{

        for(int i = 0; i < N; i++){
            
            p[row] = i;     // (row, i) 위치에 놓은 말
            
            if ( IsPromising(row)){ // 현재 줄에 말을 옮은 위치에 놓았으면

                N_queen(row+1); // 다음 줄에 말을 놓는다
            }
        }
    }
}

int main(){
    
    cin >> N;

    N_queen(0);

    cout << cnt;

    return 0;
}