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

이런 방식으로 이 조합을 나열하는 알고리즘은 다양하게 만들 수 있습니다(물론 간단히 만들어
지는 건 아닙니다). 그러면 처음으로 다시 돌아가 문제를 정리하기 위해 먼저 [규칙 1]에 따라 조
합을 나열하는 알고리즘을 생각해 보겠습니다.

그림 5-15는 퀸을 놓기 직전의 상태입니다. 그림 안의 ‘?’는 그 열에 퀸이 아직 배치되지 않았

음을 의미합니다.

모든 열에 퀸이 아직 배치되지 않은 상태.
퀸을 배치해 ‘?’를 해결하세요.
？ ？ ？ ？ ？ ？ ？ ？

[그림 5-15] 각 열에 퀸을 1개만 배치한 원래 문제

처음에는 모든 열이 ‘?’이고 8열 모두 ‘?’를 채우면 퀸 배치가 완료됩니다. 우선 0열에서의 퀸

배치를 검토하겠습니다. 그림 5-16을 보면 0열에서의 퀸의 배치 방법은 총 8가지입니다. 그
림에서 ●는 퀸이 배치된 상태를 나타냅니다. 그림 5-16 1 ~ 8 의 각 그림은 모두 0열에 퀸
을 배치하고 나머지 열에는 아직 배치하지 않은 상태를 나타냅니다.
조금 어려운 말로 설명하면 그림 5-15의 ‘원래 문제’를 ‘8개의 부분 문제’로 나눈 결과가 그림 5-16입니다.

0열에 퀸을 배치했습니다. 다음은 1열에 퀸을 배치하는 방법입니다.

186 C 알고리즘