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

가지 뻗기

여기에서는 188쪽의 그림 5-18처럼 가지를 뻗으며 모든 조합을 나열하는 프로그램을 만들
어 보겠습니다.
지금은 조합만 나열하고, 8퀸 문제는 조합을 나열한 다음에 해결하겠습니다.

배열 pos는 퀸의 배치를 나타냅니다. i열에 놓인 퀸의 i열에 놓인 퀸의 위치가 j행이면 pos[i]에 j를
대입합니다.
위치가 j행이면 pos[i]의 값을 j로 합니다(그림 5-19).
예를 들어, pos[0]의 값이 0이면 ‘0열의 퀸이 0행에 배 0 1 2 3 4 5 6 7
0 ●
치된 상태’를 의미합니다. pos[1]의 값 4는 ‘1열의 퀸 1 ●
2 ●
이 4행에 배치된 상태’를 의미합니다. 3 ●
4 ●
이때 set 함수는 pos[i]에 0부터 7까지의 값을 순서대 5 ●
6 ●
로 대입하여 ‘i열에 퀸을 1개만 배치하는 8가지 조합을 7 ●
만드는 재귀 함수’입니다. 매개변수 i가 이 퀸을 배치할

열입니다. 이 함수는 가장 먼저 main 함수에서 다음과 0 4 7 5 2 6 1 3
0 1 2 3 4 5 6 7
같이 호출합니다. [그림 5-19] 퀸의 배치를 나타내는 배열

set(0);

호출된 set 함수는 매개변수 i에 0을 전달받습니다. 그리고 0열에 1개의 퀸을 배치하는 8가지

조합을 for문에 의해 나열합니다(그림 5-16). j 값을 0부터 7까지 1씩 증가하며 다음과 같이 재
귀 호출을 합니다.

set(i + 1);

set(i + 1)에 의해 앞에서 했던 작업을 다음 열인 1열에서 수행합니다. 이렇게 재귀 호출을 반
복하다가 i가 7이 되면 8개의 퀸이 모두 배치됩니다. 그러면 퀸을 더 배치할 필요가 없으므로

print 함수를 호출하여 퀸이 배치된 위치를 출력합니다. 출력하는 값은 pos의 배열 요솟값입
니다. 이렇게 프로그램을 실행하면 그림 5-18에서 볼 수 있었던 16,777,216개의 모든 조합
이 나열됩니다.

190 C 알고리즘