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

25 else {
26 flag[j] = 1;
27 set(i + 1);
28 flag[j] = 0;
29 }
30 }
31 }
32 }
33
34 int main(void)
35 {
36 int i;
37 for(i = 0; i < 8; i++)
38 flag[i] = 0;
39 set(0);
40
41 return 0;
42 }

실습 5-8의 프로그램은 flag라는 배열을 사용합니다. flag는 같은 행에 중복하여 퀸이 배치되
는 것을 방지하기 위한 표시(flag)입니다. j행에 퀸을 배치하면 flag[j]의 값을 1로 하고, 배치되

지 않은 상태의 값은 0으로 합니다. 그러면 좀 더 자세히 살펴보겠습니다. 0열에 퀸을 배치하
기 위해 호출한 set 함수는 먼저 0행에 퀸을 배치합니다(flag[0]의 값은 0입니다). 0행에 퀸을 배
치했기 때문에 flag[0]의 값을 1로 변경합니다. 그런 다음 set 함수를 재귀적으로 호출합니다.
이렇게 호출한 set 함수는 다음 1열에 퀸을 배치합니다(그림 5-20).

0행 0열에 퀸을 배치한 상태에서 1열에 퀸을 배치하는 과정

a ● ０ 1 0행에 이미 퀸을 배치했습니다.
１ 0 이 조합은 생각할 필요가 없습니다.
２ 0
？ ？ ？ ？ ？ ？ ３ 0
４ 0
５ 0
６ 0
７ 0
b ● ０ 1 1행에 퀸을 아직 배치하지 않았습니다.
１ 0
２ 0 1행에 퀸을 배치합니다.
３ 0
？ ？ ？ ？ ？ ？
４ 0
５ 0
６ 0
７ 0
…
[그림 5-20] flag 배열을 사용한 한정 조작

05•재귀 알고리즘 193