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

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

가장 먼저 출력되는 ‘0 0 0 0 0 0 0 0’은 모든 퀸이 0행에 배치되었음을 보여줍니다(그림 5-18의 No.1). 가장 마지막에
출력되는 ‘7 7 7 7 7 7 7 7’은 모든 퀸이 7행에 배치되었음을 보여줍니다(그림 5-18의 No.16, 777, 216).

이렇게 가지를 뻗으며 퀸을 배치하는 조합을 모두 나열했습니다. 이러한 방법을 가지 뻗기
(branching)라고 합니다. 하노이의 탑이나 8퀸 문제처럼 문제를 세분하고 세분된 작은 문제의

풀이를 결합해 전체 문제를 풀이하는 기법을 분할 해결법(divide and conquer)이라고 합니다.

05•재귀 알고리즘 191