[9663번] N-Queen

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

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

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

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

[예제입력] 8

[예제출력] 92

[풀이를 위한 개념]

백트래킹이란 경우의 수를 모두 조사하는 알고리즘입니다. 트리구조 데이터에서 탐색하는 과정인데 깊이우선탐색(DFS)를 기반으로 합니다. 그 이유는 백트래킹은 어떤 Node를 조사했을 때, 유망한 Node면 깊이 탐새하고 유망한 Node가 아닐 경우는 부모 노드로 돌아가는 방식을 채택하기 때문입니다.

즉, 조건에 맞을 때까지 깊이 탐색하는 과정은 DFS와 같지만 매 Node마다 가능성을 체크해서 계산 숫자를 줄이는 방법을 백트래킹이라고 합니다. (가능성을 체크해서 경우의 수를 줄이는 걸 '가지치기'라고 한다.)

[그림1] 가지치기로 경우의 수와 계산 횟수를 줄일 수 있다.

[풀이과정]

퀸은 대각선 방향과 위아래 방향 거리에 상관없이 모두 이동할 수 있습니다..

그렇기 때문에 퀸은 서로 같은 행이나 열에 위치할 수 없습니다. 이 조건만 있어도 문제가 굉장히 단순화 됩니다.

NxN의 체스판이 있을 때, 한 층에 퀸 한 개만 둘 수 있다는 조건이기 때문입니다.

[그림2] 체스판에서 한층씩 올라가면서 가능여부를 따지고 가지치기를 한다.

재귀함수를 이용해서 해당층의 열(column)을 모두 방문하면서 가능여부를 따집니다. 

1. 방문한 곳을 true 표시한다.

2. 행(row)을 +1해서 다시 재귀함수를 실행한다.(자식 node로 이동)

3. 가능하지 않은 곳을 마주치면 여태 방문한 node를 모두 false 처리하고 다음으로 이동한다. (false 처리해야 다른 가지에서 다시 타고 내려올 때 해당 node에서 가능여부를 다시 따질 수 있게 됩니다.) 

왔던 흔적을 지우고 부모node로 이동해서 다음 node로 실행되므로 이 부분을 백트래킹(back-tracking)이라고 합니다.

 

[정답]

#include<iostream>
 
 
using namespace std;
 
int n;
bool a[15][15];
int ans = 0;
 
 
 
bool check(int row, int col)    //퀸의 이동영역에 겹치는지 확인하는 함수
{
    for(int i =0;i<n;i++)        //직선방향 확인
    {
        if(i == row) continue;
        if(a[i][col])
        {
            return 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 calc(int row)
{
    if(row == n)                //끝까지 도착하면 가능한 경우이므로 정답
    {
        ans += 1;
    }
 
    for(int col = 0; col < n; col++)        //모든 열(column) 방문
    {
        a[row][col] = true;
        if(check(row, col))
        {
            calc(row+1);        //다음 행(row)로 이동
        }
        a[row][col] = false;    //백트래킹 (방문했던 흔적을 지우고 '가지치기' 한다)
    }
}
 
int main()
{
    cin >> n;
    calc(0);
    cout << ans << endl;
 
    return 0;
}

위 답에서 시간복잡도를 줄이는 방법(클릭시 다른 포스팅이 새창으로 열립니다.)

아래는 재귀 함수가 진행되는 순서를 작성했습니다. (참고용)

Two Earth_)

궁금한건 질문해주시고 틀린부분은 지적해주시면 감사하겠습니다 

1. 아직까지 재귀함수나 DFS의 풀이방법이라는 걸 알아차리기가 힘들다.

세번째는, 재귀를 이용한 DFS.