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

flag_b와 flag_c는 ‘/’ 방향과 ‘ / ’ 방향의 대각선 위에 퀸을 배치했는지 체크하는 배열입니다

(그림 5-21).
실습 5-9의 프로그램에서는 실습 5-8의 배열 이름 flag를 flag_a라고 바꾸었습니다.

a 배열 flag_b에 대응하는 라인 b b b 배열 flag_c에 대응하는 라인
0 1 2 3 4 5 6 7 7 8 9 10 11 12 13 14
8 6
9 5
10 4
11 3
12 2
13 1
14 0

j행 i열의 값은 i + j로 구합니다. j행 i열의 값은 i - j + 7로 구합니다.

[그림 5-21] 대각선에 퀸 배치하기

그림 5-21에서 볼 수 있듯이 j행 i열에서 각각의 대각선 방향에 대해 퀸이 배치되었을 때 체크
하는 배열의 인덱스는 flag_b[i + j]와 flag_c[i – j + 7]입니다. 각 칸에 퀸의 배치를 체크할 때

같은 행에 퀸을 배치했는지 판단하고 그런 다음 이 그림( a , b )의 점선 위에 퀸을 배치했는지
검사합니다(실습 5-9의 회색으로 표시한 부분 참고).

가로 방향(같은 행), 왼쪽 대각선 방향, 오른쪽 대각선 방향 중 어느 방향이든 1개의 라인이라

도 퀸이 배치되었다면 그 칸에는 퀸을 놓을 필요가 없습니다. 이 경우 초록색으로 표시한 부
분(실습 5-9)의 실행을 건너뜁니다. 3개의 배열(flag_a, flag_b, flag_c)을 사용하는 한정 조작을
수행하면 8퀸 문제의 조건을 만족하는 퀸의 배치를 효율적으로 수행할 수 있습니다. 프로그

램을 실행하면 92개의 조합이 출력됩니다.
모든 프로그램의 main 함수에서 flag용 배열 요소에 0을 대입하는 for문은 생략할 수 있는데, 이는 함수 외부에서 선언한
변수는 항상 0으로 초기화되기 때문입니다.

연습 Q8 실습 5-9의 print 함수를 수정하여 전각 기호 ‘■’와 ‘□’를 사용 ■ □ □ □ □ □ □ □
문제 해 퀸의 배치 상황을 출력하세요. □ □ □ □ □ □ ■ □
□ □ □ □ ■ □ □ □
□ □ □ □ □ □ □ ■
□ ■ □ □ □ □ □ □
□ □ □ ■ □ □ □ □
□ □ □ □ □ ■ □ □
□ □ ■ □ □ □ □ □
Q9 8퀸 문제를 비재귀적으로 구현한 프로그램을 작성하세요.

196 C 알고리즘