Page 192 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

물론 문제를 세분할 때는 작은 문제의 풀이에서 원래 문제의 풀이가 쉽게 도출(導出)될 수 있

게 설계해야 합니다.
06장에서 학습하는 빠른 정렬(quicksort)과 병합 정렬(mergesort)도 분할 해결 알고리즘입니다.

분기 한정법
가지 뻗기로 퀸을 배치하는 조합을 나열할 수는 있지만 8퀸 문제의 답을 얻을 수는 없습니다.
다음은 앞에서 분기를 한정하기 위해 정했던 규칙입니다.

[규칙 2] 각 행에 퀸을 1개만 배치합니다.

이 개념을 적용하여 다시 살펴보겠습니다.

실습 5-8 •완성 파일 chap05/queen_bb.c
01 /* 각 행, 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열합니다. */
실행 결과
02 #include <stdio.h>
0 1 2 3 4 5 6 7
03
0 1 2 3 4 5 7 6
04 int flag[8]; /* 각 행에 퀸을 배치했는지 체크하는 배열 */ 0 1 2 3 4 6 5 7
05 int pos[8]; /* 각 열에서 퀸의 위치 */ 0 1 2 3 4 6 7 5
06 0 1 2 3 4 7 5 6
07 /*--- 각 열에서 퀸의 위치를 출력 ---*/ 0 1 2 3 4 7 6 5
0 1 2 3 5 4 6 7
08 void print(void)
0 1 2 3 5 4 7 6
09 {
0 1 2 3 5 6 4 7
10 int i; 0 1 2 3 5 6 7 4
11 for(i = 0; i < 8; i++) … 중략 …
12 printf("%2d", pos[i]); 7 6 5 4 3 2 1 0
13 putchar('\n');
14 }
15
16 /*--- i열에서 알맞은 위치에 퀸을 배치 ---*/
17 void set(int i)
18 {
19 int j;
20 for(j = 0; j < 8; j++) {
21 if(!flag[j]) { /* j행에 퀸을 배치하지 않았다면 */
22 pos[i] = j;
23 if(i == 7) /* 모든 열에 배치를 마침 */
24 print();

192 C 알고리즘