[Programmers] N-Queen

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

---

 

문제 해결 과정

착안

체스판 내에서의 퀸의 이동 법칙에 따라 한 줄마다 하나의 퀸만 놓을 수 있으므로, 가장 위쪽 줄부터 시작하여 아래쪽으로 한 줄씩 퀸을 순차적으로 배치하여 문제를 해결할 수 있다.

 

이때, 각 줄마다 퀸을 배치할 수 있는 칸이 있는지 확인하여 배치할 수 있는 경우에는 퀸을 배치, 그렇지 않은 경우에는 현재 줄에서 배치한 퀸을 다시 회수하고 이전 단계로 되돌아가는 백트래킹(backtracking) 알고리즘을 구현하여 문제를 해결할 수 있다.

 

추가적으로, 가장 위쪽 줄부터 순차적으로 퀸을 하나씩 배치하는 경우에는 각 줄마다의 퀸이 공격 가능한 경로를 전부 표시하거나 계산할 필요 없이 아래 방향으로 공격이 가능한 경로만 파악해도 문제를 해결할 수 있다.

• 각 줄마다 퀸을 하나 이상 배치할 수 없으므로, 가로 방향으로 공격 가능한 경로의 계산이 불필요하다.
• 위에서 아래 방향으로 순차적으로 배치하기 때문에 위쪽 방향으로 공격 가능한 경로의 계산이 불필요하다.

 

구현

현재 단계에서 배치된 퀸의 공격 가능한 경로를 표시하거나, 다시 이전 단계로 되돌리는 과정을 구현하는 데에 있어 편의상 체스판을 int 형의 2차원 배열로 표시하고, 퀸을 배치할 때마다 공격 가능한 경로에 해당하는 칸의 값을 1씩 증가시키거나 감소하는 방식을 사용하여 문제를 해결하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

int ChessBoard[12][12];
int Queens;
int Count;

void AddQueen(int n, int col, int inc)
{
    // 퀸을 배치하는 곳 = ChessBoard[Queens][col]
    
    // 아래 방향 이동 경로 표시 (아래 방향 직선 및 왼쪽/오른쪽 대각선)
    if (Queens < n - 1)
    {
        int side = 1;
        for (int k = Queens + 1; k < n; k++)
        {
            ChessBoard[k][col] += inc;
            if (col - side >= 0)
                ChessBoard[k][col - side] += inc;
            if (col + side < n)
                ChessBoard[k][col + side] += inc;
            side++;
        }
    }
}

void PlayChess(int n)
{
    if (Queens == n)
    {
        Count++;
        return;
    }

    for (int i = 0; i < n; i++)
        if (ChessBoard[Queens][i] == 0)
        {
            AddQueen(n, i, 1);
            Queens++;
            PlayChess(n);
            Queens--;
            AddQueen(n, i, -1);
        }
}

int solution(int n)
{
    PlayChess(n);
    return Count;
}

 

실행 결과