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

for문은 0행부터 7행까지 퀸을 배치합니다. 다음의 a , b 는 그림 5-20에 대한 설명입니다.

a 0행에 퀸을 배치하는 방법입니다. flag[0]의 값이 1이므로 이 행에는 퀸을 이미 배치했음
을 알 수 있습니다. 따라서 여기에는 배치하지 않습니다. 그 결과 점선으로 둘러싼 부분(그림
5-18)에 있는 262,144개의 조합이 완전히 생략됩니다. 색칠한 부분은 배치를 건너뜁니다. 다

시 말해 set 함수를 재귀 호출하지 않습니다.

b 1행에 퀸을 배치하는 방법입니다. flag[1]의 값이 0이므로 이 행에는 퀸을 아직 배치하지

않았습니다. 1행에 퀸을 배치합니다(색칠한 부분). 다시 말해 set 함수를 재귀 호출하여 다음 열
인 2번째에 퀸을 배치합니다.
2행부터 7행까지도 이와 같은 방법을 사용해 퀸을 배치합니다.

또 재귀 호출한 set(i + 1) 함수가 끝나면 퀸을 j행에서 제거했기 때문에 flag[j]에 아직 배치하

지 않았음을 나타내는 0을 대입합니다. set 함수에서는 퀸을 배치하지 않은 행(flag[j]의 값이 0
인 행)에만 퀸을 배치합니다. 이처럼 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법
을 한정(bounding) 조작이라 하고, 가지 뻗기와 한정 조작을 조합하여 문제를 풀어 가는 방법
을 분기 한정법(branching and bounding method)이라고 합니다.

8퀸 문제를 푸는 프로그램

실습 5-8의 프로그램은 퀸이 행 방향과 열 방향으로 겹쳐지지 않는 조합을 나열(출력)하기만
했습니다. 이런 경우는 ‘8퀸 문제를 풀었다.’가 아니라 ‘8룩(Rook) 문제를 풀었다.’라고 말할
수 있습니다. 퀸은 대각선 방향으로도 이동할 수 있기 때문에 어떤 대각선에서 보더라도 퀸을
1개만 배치하는 한정 조작을 추가해야 합니다.

실습 5-9 •완성 파일 chap05/eight_queen.c

01 /* 8퀸 문제 풀이 */
02 #include <stdio.h>
03
04 int flag_a[8]; /* 각 행에 퀸을 배치했는지 체크하는 배열 */
05 int flag_b[15]; /* 대각선 /에 퀸을 배치했는지 체크하는 배열 */
06 int flag_c[15]; /* 대각선 \에 퀸을 배치했는지 체크하는 배열 */
07 int pos[8]; /* 각 열에서 퀸의 위치 */
08

194 C 알고리즘