[백준/C언어] 9663번 - N-Queen

백준 웹사이트 "9663번 - N-Queen" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

9663번: N-Queen

---

소스 코드

#include <stdio.h>
#include <math.h>

int N_queen(int num, int N, int * board);

int main(void){
    int N;
    scanf("%d", &N);

    int board[N];   //(i, board[i])가 queen의 위치
    for(int i=0; i<N; i++){
        board[i]=0;
    }

    printf("%d\n", N_queen(0, N, board));
}

int N_queen(int num, int N, int * board){
    if(num==N)
        return 1;
    else{
        //count: 경우의 수
        int count=0;
        //num 번째 줄에 queen 위치
        for(int i=0; i<N; i++){
            //0~num-1 번째 줄에 겹치는 queen 있는가 확인
            int overlap = 0;
            for(int j=0; j<num; j++){
                int column = board[j];  //queen의 위치: (j, column)
                if(column==i || abs(num-j)==abs(i-column)){
                    //printf("num, i, j, column: %d %d %d %d\n", num, i, j, column);
                    overlap = 1;
                    break;
                }
            }
            if(!overlap){   //겹치지 않을 경우
                //printf("queen position: %d, %d\n", num, i);
                board[num]=i;
                count += N_queen(num+1, N, board);
            }
        }
        return count;
    }
}

---

문제 풀이

  대표적인 백트래킹 문제 중 하나인 'N-Queen' 문제입니다. N×N 판에 서로 공격당하지 않도록 N개의 퀸을 놓는 문제로, 퀸을 하나씩 차례로 놓아보면서 알맞은 위치를 찾아야 합니다.

  가장 먼저 배열 'board'를 선언/초기화합니다. 이는 퀸의 위치를 기록하는 배열로, (i, board[i])가 퀸의 위치입니다. 즉, i번째 줄의 퀸은 board[i]번째 칸에 위치한다는 의미입니다. 서로 공격하지 않으려면 한 줄에는 정확히 하나의 퀸만 들어가야 하기 때문에 여러 개의 퀸이 속할 경우는 없습니다.

  'N-queen' 재귀함수는 다음과 같이 정의합니다.

함수: N_queen(int num, int N, int * board)
- 반환: N×N 판에 N개의 퀸을 서로 공격하지 않게 위치시키는 경우의 수

파라미터
- num : 재귀 반복 횟수 (현재 재귀 단계까지 놓은 퀸의 개수)
- N : 놓아야 하는 최대 퀸 개수 (판의 크기도 N×N)
- board : 퀸의 위치를 기록하는 배열. i번째 줄의 퀸은 board[i]에 위치하므로 (i, board[i])가 queen의 위치

Base Case (기본 케이스)
- 조건문: num == N
- 실행문: 1을 반환 (조건을 만족하는 경우이므로, 경우의 수 증가)

Recursive Case (재귀 케이스)
- 조건문: num != N (num이 N보다 작을 경우)
- 실행문: num 번째 줄의 각 칸에 퀸을 위치시켜보며 이전 줄과 겹치는가 확인. 겹치지 않을 경우, board[num]에 해당 위치를 기록한 후 재귀
- 재귀: N_queen(num+1, N, board)

 

  N-queen 재귀함수의 재귀 케이스를 봅시다. Line 25의 for문을 통해 num번째 줄의 퀸을 각 칸에 위치시켜 봅니다. 퀸을 칸 'i'에 위치시켰다고 가정할 경우, 0 ~ num-1번째 줄의 퀸들에게 공격당하지 않는지 검사해봐야 합니다. 이는 Line 30의 if문을 통해 검사하는데, 같은 열에 있을 경우 column==i를 만족하고, 같은 대각선 상에 있을 경우 abs(num-j)==abs(i-column)을 만족합니다. 만약 이전 퀸들에게 공격을 당하는 위치라면 퀸은 칸 'i'에 존재하지 못합니다. 반면, 이전 퀸들에게 공격을 당하지 않는 위치라면 board[num]=i를 통해 퀸을 위치시키고, 업데이트된 새로운 board로 재귀를 진행합니다.

  이 문제를 풀 때, 처음에 저는 board를 N×N 이차원 배열로 선언하여 실제 N×N 판을 구현했습니다. 이렇게 이차원 배열로도 문제 풀이가 가능하지만, 일차원 배열을 이용할 때에 비해 훨씬 오랜 시간이 걸립니다. 이렇듯 알고리즘이 똑같해도 시간 차이가 많이 날 수 있으며, 최적화시킬 수 있는 방법을 찾는 것이 중요합니다.