알고리즘 기초 연습문제 5장 해설

2. n-여왕말 문제를 푸는 되추적 알고리즘(알고리즘 5.1)을 문제 사례가 n=8인 경우 ... 상태공간트리를 그리시오.

n-여왕 문제는 체스판 위에 n개의 여왕을 서로 공격할 수 없도록 배치하는 문제이다. 여왕은 가로, 세로, 대각선으로 공격할 수 있기 때문에, 한 여왕이 다른 여왕과 같은 행, 열, 대각선에 놓이지 않도록 주의해야 한다. 이를 해결하기 위해 되추적 알고리즘을 사용할 수 있다. n=8인 경우를 예로 들어 설명하겠다. 8-여왕 문제를 푸는 방법은 체스판의 각 행에 여왕을 하나씩 배치하며 조건을 검사하는 방식이다. 상태 공간 트리는 해결 과정에서 여왕을 놓는 다양한 선택지와 그에 따른 경과를 시각화한 구조이다. 이 경우에는 8개의 행을 고려하며, 각 행마다 여왕을 배치할 수 있는 위치를 선택하게 된다. 먼저, 첫 번째 행에 여왕을 놓는 방법부터 시작한다. 체스판의 좌표 시스템을 사용하여 각 위치를 (행, 열)로 표기하면 첫 번째 행의 여왕은 (0, 0), (0, , (0, ,. . , (0, 위치에 놓을 수 있다. 각 위치에 여왕을 배치할 때마다 다음 행으로 넘어가며 여왕을 안전하게 놓을 수 있는지 판단한다. 상태 공간 트리는 DFS(깊이 우선 탐색) 방식으로 …