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

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
●
●

●
No.1 No.2 No.3 … No.8

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ● ● ● ●
●

●
No.9 No.10 No.11 … No.16
…
중략
… ●
●
●

● ● ● ● ● ● ●
No.16,777,210
No.16,777,211
No.16,777,209 ● ● ● ● ● ● ● ● ● ● ● ● ● ● … No.16,777,216 ● ● ● ● ● ● ● ●
[그림 5-13] 퀸을 각 열에 1개만 배치한 조합

그래서 다음 규칙을 추가합니다.

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

그림 5-14는 앞에서 소개한 그림의 배치 가운데 [규칙 2]를 만족하는 배치의 일부(네 가지)를
나타낸 것입니다. 이렇게 하면 조합의 개수는 더 줄어듭니다.

● ● ● ●
● ● ● ●
● ● ● ●
● ● ● ●
● ● ● ●
● ● ● ●
● ● ● ●
● ● ● ●
…
[그림 5-14] 퀸을 각 행과 열에 1개만 배치한 조합

05•재귀 알고리즘 185