[C] 분할 해결법과 분기 한정법을 활용한 8퀸 문제 풀이(n퀸 문제)

김태희·2023년 12월 21일
C자료구조와 알고리즘
0

C로 배우는 자료구조와 알고리즘 시리즈

목록 보기
25/31
post-custom-banner

8퀸 문제(8-Queen problem)

서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓으세요.



8 x 8 체스판에서 퀸을 놓는 경우의 수

64칸이 있는 체스판에서 8개의 퀸을 아무런 규칙 없이 배열하는 경우의 수를 계산하자면 아래와 같다.

64 * 63 * 62 * 61 * 60 * 59 * 58 * 57 = 178,462,987,637,760

하지만 이와 같은 경우의 수를 다 조사해볼 수는 없을 것이다.

경우의 수를 줄이기 위해 퀸이 같은 행이나 열 그리고 대각선에 있는 경우를 제외하고 조사할 것이다.


가지 뻗기(branching)와 분할 해결법(divide and conquer)

경우의 수를 줄이기 위해 해결해야하는 조건들을 정리해보자.

  1. 각 열에 퀸을 1개만 배치한다.
    8^8 = 16,777,216

  2. 각 행에 퀸을 1개만 배치한다.

  3. / 대각선마다 퀸을 하나 씩 배치한다.

  4. \(역 슬래시) 대각선마다 퀸을 하나 씩 배치한다.

프로그램 설계

배열 pos는 퀸의 배치를 나타내고 i열에 놓인 퀸의 위치가 j행이면 pos[i]의 값은 j이다.

이와 같은 형태의 pos 배열은 나중에 행과 열의 합이나 차가 같은 경우에 같은 대각선에 위치한다는 점을 활용할 수 있게 한다.

pos[i]에 0부터 7까지의 값을 순서대로 대입하여 i열에 퀸을 1개만 배치하는 8가지 조합을 만드는 set 함수를 구현해보겠다.

#include <stdio.h>

int pos[8] = { 0, }; 

void print(){ //각 열의 퀸 위치를 출력
  for(int i=0; i<8; i++) printf("%2d", pos[i]);
  putchar('\n');
}

void set(int i){ //i열(|)
  for(int j=0; j<8; j++){ //j행(ㅡ)
    pos[i] = j;
    if(i == 7) print(); //모든 열의 배치를 마치는 경우
    else set(i+1); //다음 열에 퀸을 배치
  }
}

int main(void){
  set(0); //0 열에 퀸을 배치

  return 0;
}
----------------------------------------------
결과
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 4
.....
0 0 0 0 0 0 0 7
0 0 0 0 0 0 1 0
.....
7 7 7 7 7 7 7 6
7 7 7 7 7 7 7 7

0 0 0 0 0 0 0 0은 모든 퀸이 0행에 배치되었음을 의미한다.

재귀를 활용해 각 열에 1개의 퀸을 배치시키는 가지 뻗기를 해본 결과 16,777,216개의 모든 조합이 나열되었다.

전에 다뤘던 '하노이의 탑'이나 이 코드처럼 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법을 분할 해결법이라고 한다.

이런 분할 해결법을 사용할 때 작은 문제의 풀이에서 원래 문제의 풀이가 쉽게 도출될 수 있도록 설계해야한다.


한정 조작(bounding)과 분기 한정법(branching and bounding method)

가지 뻗기에서 퀸을 배치하는 모든 조합을 나열했다. 여기서 분기(branch)는 가지 뻗기에서 뻗은 가지들을 의미한다.

이러한 가지(분기)들 중 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법을 한정 조작이라고 하고 가지 뻗기와 한정 조작을 조합하여 문제를 풀어나가는 방법을 분기 한정법이라고 한다.

각 열에 1개의 퀸만 배치시키는 가지 뻗기를 했으니 각 행에도 1개의 퀸만 배치하도록 분기를 한정해보자.

#include <stdio.h>

int flag[8] = { 0, }; // 각 행에 퀸을 배치했는지 체크하는 배열
int pos[8] = { 0, }; // 각 열에서 퀸의 위치

void print(){
  for(int i=0; i<8; i++) printf("%2d", pos[i]);
  putchar('\n');
}

void set(int i){ //i열(|)
  for(int j=0; j<8; j++){ //j행(ㅡ)
    if(flag[j] == 0){
      pos[i] = j;
      if(i == 7) print(); //모든 열의 배치를 마치는 경우
      else{
        flag[j] = 1;
        set(i+1); //다음 열에 퀸을 배치
        flag[j] = 0;
      } 
    }
  }
}

int main(void){
  set(0);

  return 0;
}

----------------------------
결과

0 1 2 3 4 5 6 7
0 1 2 3 4 5 7 6
0 1 2 3 4 6 5 7
0 1 2 3 4 6 7 5
0 1 2 3 4 7 5 6
0 1 2 3 4 7 6 5
0 1 2 3 5 4 6 7
0 1 2 3 5 4 7 6
...............
7 6 5 4 3 2 1 0

호출 순서

첫 번째 호출 : set(0)이 호출된다. 이때, 첫 번째 열에 퀸을 배치하려고 시도한다.

flag 배열에 해당 행에 퀸을 배치했다는 표시를 하고 set(1)을 호출한다.

두 번째 호출: set(1)에서는 두 번째 열에 퀸을 배치하려고 시도한다.

가능한 행을 찾아 flag 배열에 표시하고 set(2)를 호출하고 이 과정이 계속해서 열마다 반복된다.

퀸의 배치 완료: set(7)에서 일련의 재귀 호출을 통해 여덟 번째 열까지 퀸의 배치를 완료하게 된다.

여덟 번째 열까지 퀸을 배치했으므로 print() 함수를 호출하여 현재의 퀸의 배치를 출력한다.

이전 단계로 돌아가면서 다른 가능한 퀸의 배치를 찾는다.

이때, flag 배열에서 이전에 표시한 퀸의 배치를 지워나가면서 백트래킹을 수행한다.

이렇게 계속해서 모든 가능한 퀸의 배치를 찾을 때까지 반복된다.

재귀는 정말 어려운 것 같다.

코드를 직접 짠 것도 아니고 예제를 따라 학습하였는데도 이를 이해하는데만 한참이 걸렸다.

이해한 후 아래부터는 연습할겸 직접 코드를 짜보았다.


8퀸 문제를 푸는 프로그램 구현

구현 시 유의한 점

1. / 대각선의 퀸 배치 가능 여부
행과 열의 합이 같으므로 i + j의 값(0~14)을 저장하는 flag_l[15]에 저장

ex) 2행 0열, 1행 1열, 0행 2열은 / 대각선에 위치한다.

2. \(역슬래시) 대각선의 퀸 배치 가능 여부
행과 열의 차가 같으므로 배열에서 사용하기 위해 i - j(-7~7)에다가 7을 더하여 사용하고 i - j + 7의 값(0~14)을 저장하는 flag_r[15]에 저장

ex) 1행 1열, 2행 2열, 3행 3열.....은 \ 대각선에 위치한다.

이 두 가지를 고려하여 앞서 구현한 코드에다 종료 조건식을 추가해주었다.

그리고 총 반복 횟수를 세기 위해 set 함수에 매개변수를 추가해 열이 완성되어 출력될 때마다 count++ 를 해주었다.

#include <stdio.h>

int flag_h[8] = { 0, }; // 각 행에 퀸을 배치했는지 체크하는 배열
int flag_l[15] = { 0, }; // '/'
int flag_r[15] = { 0, }; // '\'
int pos[8] = { 0, }; // 각 열에서 퀸의 위치

void print(){ //출력
  for(int i=0; i<8; i++) printf("%2d", pos[i]);
  putchar('\n');
}


void set(int i, int *a){
  for(int j=0; j<8; j++){
    if(flag_h[j] == 0 && flag_l[i+j] == 0 && flag_r[i-j+7] == 0){
      pos[i] = j;
      if(i == 7){
        print();
        (*a)++;
      }
      else{
        flag_h[j] = flag_l[i+j] = flag_r[i-j+7] = 1;
        set(i + 1, a);
        flag_h[j]= flag_l[i+j] = flag_r[i-j+7] = 0;
      }
    }
  }
}

int main(void){
  int count = 0;
  set(0, &count); //0 열에 퀸을 배치
  printf("가능한 8퀸 배치 수 : %d", count);
  return 0;
}

--------------------------------------------------------------
결과 

0 4 7 5 2 6 1 3
0 5 7 2 6 3 1 4
0 6 3 5 7 1 4 2
0 6 4 7 1 3 5 2
1 3 5 7 2 0 6 4
1 4 6 0 2 7 5 3
1 4 6 3 0 7 5 2
1 5 0 6 3 7 2 4
1 5 7 2 0 3 6 4
1 6 2 5 7 4 0 3
1 6 4 7 0 3 5 2
1 7 5 0 2 4 6 3
...............
7 3 0 2 5 1 6 4
가능한 8퀸 배치 수 : 92

이렇게 보면 고생해서 만든 프로그램이 정작 눈에는 잘 들어오지 않는다.

□과 ■를 활용해 체스판처럼 눈에 보여지게 프로그램을 구현해보자.


#include <stdio.h>

int flag_h[8] = { 0, }; // 각 행에 퀸을 배치했는지 체크하는 배열
int flag_l[15] = { 0, }; // '/'
int flag_r[15] = { 0, }; // '\'
int pos[8] = { 0, }; // 각 열에서 퀸의 위치

void print(){ //출력
  for(int i=0; i<8; i++){
    for(int j=0; j<8; j++){
      if(pos[i] == j){
        printf("■ ");   
      }else{
        printf("□ ");
      }
    }
    putchar('\n');
  }
  printf("\n----------------\n");
}


void set(int i, int *a){
  for(int j=0; j<8; j++){
    if(flag_h[j] == 0 && flag_l[i+j] == 0 && flag_r[i-j+7] == 0){
      pos[i] = j;
      if(i == 7){
        print();
        (*a)++;
      }
      else{
        flag_h[j] = flag_l[i+j] = flag_r[i-j+7] = 1;
        set(i + 1, a);
        flag_h[j]= flag_l[i+j] = flag_r[i-j+7] = 0;
      }
    }
  }
}

int main(void){
  int count = 0;
  set(0, &count); //0 열에 퀸을 배치
  printf("가능한 8퀸 배치 수 : %d", count);
  return 0;
}

-----------------------------------------------------
결과

■ □ □ □ □ □ □ □ 
□ □ □ □ ■ □ □ □ 
□ □ □ □ □ □ □ ■ 
□ □ □ □ □ ■ □ □ 
□ □ ■ □ □ □ □ □ 
□ □ □ □ □ □ ■ □ 
□ ■ □ □ □ □ □ □ 
□ □ □ ■ □ □ □ □ 

----------------
■ □ □ □ □ □ □ □ 
□ □ □ □ □ ■ □ □ 
□ □ □ □ □ □ □ ■ 
□ □ ■ □ □ □ □ □ 
□ □ □ □ □ □ ■ □ 
□ □ □ ■ □ □ □ □ 
□ ■ □ □ □ □ □ □ 
□ □ □ □ ■ □ □ □ 

----------------
■ □ □ □ □ □ □ □ 
□ □ □ □ □ □ ■ □ 
□ □ □ ■ □ □ □ □ 
□ □ □ □ □ ■ □ □ 
□ □ □ □ □ □ □ ■ 
□ ■ □ □ □ □ □ □ 
□ □ □ □ ■ □ □ □ 
□ □ ■ □ □ □ □ □ 

----------------
■ □ □ □ □ □ □ □ 
□ □ □ □ □ □ ■ □ 
□ □ □ □ ■ □ □ □ 
□ □ □ □ □ □ □ ■ 
□ ■ □ □ □ □ □ □ 
□ □ □ ■ □ □ □ □ 
□ □ □ □ □ ■ □ □ 
□ □ ■ □ □ □ □ □ 

...............

----------------
가능한 8퀸 배치 수 : 92

이렇듯 알고리즘이 올바르게 구현되었음을 시각적으로도 확인할 수 있었다.

이해하는데만 엄청나게 걸린 이 알고리즘을 이 정도로만 사용하고 넘어가기는 아까워서 n값을 입력받아 n퀸 문제를 풀어주는 프로그램을 만들어보았다.


n개의 퀸을 배치하는 프로그램

#include <stdio.h>

int flag_h[800] = { 0, }; // 각 행에 퀸을 배치했는지 체크하는 배열
int flag_l[1500] = { 0, }; // '/'
int flag_r[1500] = { 0, }; // '\'
int pos[800] = { 0, }; // 각 열에서 퀸의 위치

void print(int n){ //출력
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(pos[i] == j){
        printf("■ ");   
      }else{
        printf("□ ");
      }
    }
    putchar('\n');
  }
  printf("\n----------------\n");
}


void set(int i, int n, int *a){
  for(int j=0; j<n; j++){
    if(flag_h[j] == 0 && flag_l[i+j] == 0 && flag_r[i-j+n-1] == 0){
      pos[i] = j;
      if(i == n-1){
        print(n);
        (*a)++;
      }
      else{
        flag_h[j] = flag_l[i+j] = flag_r[i-j+n-1] = 1;
        set(i + 1, n, a);
        flag_h[j]= flag_l[i+j] = flag_r[i-j+n-1] = 0;
      }
    }
  }
}

int main(void){
  int n, count = 0;
  printf("체스판을 n * n으로 만듭니다\nn의 값 : ");
  scanf("%d", &n);

  set(0, n, &count); //0 열에 퀸을 배치
  printf("가능한 %d퀸 배치 수 : %d", n, count);
  return 0;
}


----------------------------------------------
결과

체스판을 n * n으로 만듭니다
n의 값 : 4
□ ■ □ □ 
□ □ □ ■ 
■ □ □ □ 
□ □ ■ □ 

----------------
□ □ ■ □ 
■ □ □ □ 
□ □ □ ■ 
□ ■ □ □ 

----------------
가능한 4퀸 배치 수 : 2

근데 만들고 보니 앞서 배운 메모리 할당과 구조체를 이용하면 배열을 넉넉하게 만들어 놓는거보다 메모리를 줄일 수 있지 않을까라는 생각이 들었다.


구조체와 메모리 할당을 이용한 코드 최적화

하지만 어디서부터 어떻게 해야할지 감이 안 잡혀 chat gpt의 도움을 받아 코드를 최적화 시키고 이를 학습하였다.

아래는 그 결과이다.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int* flag_h; // 각 행에 퀸을 배치했는지 체크하는 배열
    int* flag_l; // '/'
    int* flag_r; // '\'
    int* pos;    // 각 열에서 퀸의 위치
} Chessboard;

void initializeChessboard(Chessboard* board, int size) {
    board->flag_h = (int*)calloc(size, sizeof(int));
    board->flag_l = (int*)calloc(2 * size - 1, sizeof(int));
    board->flag_r = (int*)calloc(2 * size - 1, sizeof(int));
    board->pos = (int*)calloc(size, sizeof(int));
}

void freeChessboard(Chessboard* board) {
    free(board->flag_h);
    free(board->flag_l);
    free(board->flag_r);
    free(board->pos);
}

void printChessboard(Chessboard* board, int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (board->pos[i] == j) {
                printf("■ ");
            } else {
                printf("□ ");
            }
        }
        putchar('\n');
    }
    printf("\n----------------\n");
}

void setQueens(int i, int size, int* count, Chessboard* board) {
    for (int j = 0; j < size; j++) {
        if (board->flag_h[j] == 0 && board->flag_l[i + j] == 0 && board->flag_r[i - j + size - 1] == 0) {
            board->pos[i] = j;
            if (i == size - 1) {
                printChessboard(board, size);
                (*count)++;
            } else {
                board->flag_h[j] = board->flag_l[i + j] = board->flag_r[i - j + size - 1] = 1;
                setQueens(i + 1, size, count, board);
                board->flag_h[j] = board->flag_l[i + j] = board->flag_r[i - j + size - 1] = 0;
            }
        }
    }
}

int main(void) {
    int n, count = 0;
    printf("체스판을 n * n으로 만듭니다\nn의 값: ");
    scanf("%d", &n);

    Chessboard board;
    initializeChessboard(&board, n);

    setQueens(0, n, &count, &board);

    printf("가능한 %d퀸 배치 수: %d\n", n, count);

    freeChessboard(&board);

    return 0;
}

결과는 내가 직접 구현한 코드와 동일하다.

이 최적화된 코드를 학습하며 함수를 더 잘 활용해 깔끔한 코드를 작성하는 방법과 변수명과 매개변수명을 설정하는 요령 등을 배울 수 있었다.

또한 구조체와 메모리 할당이 코드에서 어떻게 사용되는지 확인하며 C와 더 가까워질 수 있었다.

profile
김태희
이전 포스트

[C] void main(), int main(), 그리고 int main(void)의 차이

다음 포스트

[C] 버블 정렬 알고리즘 최적화

post-custom-banner

0개의 댓글