백준 9663. N-Queen

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

9663번: N-Queen

 

백트래킹의 가장 유명한 문제중 하나인  N-Queen 이다.

사실 이문제에서 막혀서 최근 한달정도 브루트포스, 재귀, dfs 문제만 풀었다.

한달전쯤 이문제를 풀다가 모르겠어서 다른 분들이 푼것을 봤는데 백트래킹, 특히 재귀를 이용하는 부분이 전혀 이해가 안갔다.

그 후 한달정도 재귀,dfs 관련 문제를 많이 풀었고 오늘 다시 풀어봤다.

 

한달동안 집중적으로 공부한 보람이 있었는지 쉽게 풀렸다.

 

재귀를 이용한 dfs 방식으로 첫행에 퀸을 놓는데, 

퀸은 상하좌우에 대각선까지 이동한다. 그런데 체스판의 아래방향은 아직 퀸을 놓지않았기 때문에(0번째 행부터 순서대로 놓는다)

북서, 북, 북동 방향만 탐색하면된다.

 

NQueen(depth+1) 을 호출해 다음 depth로 넘어간다. 여기서 depth는 체스판의 행번호나 마찬가지다.

마찬가지로 북서,북,북동 방향을 탐색해서 퀸이 없으면 퀸을 놓는다.

 

이렇게 퀸을 놓다가 depth가 n즉 마지막 행까지 퀸을 다 놓았다면 ans값을 1늘리고 리턴하므로

마지막에 놓았던 퀸을 다음 자리에 놓아본다. 이를 반복한다.

 

만약 depth가 n을 도달하지 못하고, 즉 마지막 행까지 퀸을 놓지 못했는데 더이상 퀸을 놓을수 있는곳이 없다면

for문이 끝에 도달하므로 이전 depth (행)으로 리턴되고 다음 칸에 퀸을 놓아볼것이다.

 

 

#include <iostream>
using namespace std;

int n;
int ans = 0;
int map[15][15];

int dr[3] = {-1, -1, -1};
int dc[3] = {-1, 0, 1};

// 북서, 북, 북동 방향 경로에 퀸있는지 탐색
bool Check(int r, int c)
{
    for(int i = 0; i < 3; i++)
    {
        int nr = r + dr[i];
        int nc = c + dc[i];
        // 체스판 범위 벗어나지 않을때까지 퀸이 있나 체크
        while(nr >= 0 && nc >= 0 && nc < n)
        {
            // 퀸이 있으므로 해당하는 자리에는 퀸을 놓을수 없음
            if(map[nr][nc] == 1) return false;
            nr += dr[i];
            nc += dc[i];
        }
    }
    return true;
}


void NQueen(int depth)
{
    if(depth == n)
    {

        ans++;
        return;
    }

    for(int i = 0; i < n; i++)
    {
        // 퀸을 놓을수 있는곳이라면
        if(Check(depth, i))
        {
            map[depth][i] = 1;

            NQueen(depth+1);

            map[depth][i]= 0;
        }
    }

}

int main()
{
    cin >> n;

    NQueen(0);

    cout << ans;
}

 

---

다른 분들 코드를 본 후에 부족했던 부분을 보충해본다.

크게 다른점은 두가지였다.

 

1. 체스판을 2차원 배열이 아닌 1차원 배열로 만든다.

1차원 배열의 인덱스를 행, 값을 열로 만들면 2차원이 아닌 1차원 배열로도 체스판의 어느 지점에 퀸을 놓았는지 표현할수 있다.

예를들어 배열이

col[0] = 0 이라면 (0,0)에 퀸을 놓았다는 뜻이고

col[2] = 3 이라면 (2,3)에 퀸을 놓았다는 뜻이다.

 

2. 퀸을 놓을수 있는지 판단하는 방법.

나는 퀸을 놓을곳으로부터 북서, 북, 북동으로 쭉 이동하면서 경로상에 퀸이 하나도 없으면 그 자리에 퀸을 놓을수 있다고 판단했다.

더 좋은 방법이 있었다, 

먼저 체스판을 나타내는 배열을 1차원 배열로 선언했기 때문에 배열에 저장되어 있는 값이 같다면 같은 열에 있다는 뜻이다.

예를들어 col[2] = 2이면 (2,2)에 퀸이 있고

col[3] = 2면 (3,2)에 퀸이있기 때문에 같은 열에 퀸이 존재하므로 퀸을 놓을수 없다.

 

대각선의 경우는 (r1, c1), (r2, c2) 두 지점을 비교할때 r1-r2 == abs(c1-c2) 라면 대각선상에 같이 존재한다.

즉 두 지점의 인덱스의 차와 값의 차가 같다면 대각선상에 같이 존재하므로 퀸을 놓을수 없다.

 

#include <iostream>
using namespace std;

int n;
int ans = 0;
// 인덱스가 행, 값이 열
// col[0] = 0 은 (0,0)에 퀸 놓음
// col[1] = 2 는 (1,2)에 퀸 놓음
int col[16] = {-1,};

// (r,c)에 퀸을 놓을수 있는지 판단
bool Check(int r, int c)
{
    // r행,c열에 퀸을 놓아봄
    col[r] = c;
    for(int i = 0; i < r; i++)
    {
        // 같은 열에 있다면 충돌함
        if(col[i] == col[r])
            return false;
        // 현재 row의 퀸과 i레벨의 퀸이 대각선에 있다면 충돌함
        else if(r-i == abs(col[r]-col[i]))
            return false;
    }
    return true;
}

void NQueen(int row)
{
    if(row == n)
    {
        ans++;
        return;
    }

    for(int i = 0; i < n; i++)
    {
        // (row,i)에 놓을수 있다면 놓는다
        if(Check(row, i))
        {
            col[row] = i;
            NQueen(row+1);
            col[row] = -1;
        }
    }
}

int main()
{
    cin >> n;

    NQueen(0);

    cout << ans;
}