[DFS] n-Queen

같은 대각선

 

대각선은 기울기가 증가하는 대각선 부분과 기울기가 감소하는 부분의 2가지 대각선이 존재한다. 이 2가지 대각선에 대해서도 체크배열을 만들어서 활용할 수 있다. 기울기가 증가하는 대각선부터 살펴보면 다음과 같다.

위 대각선 상에 있는 칸의 특징을 보면 행+열의 값이 일정하다. n이 4일 경우 행+열의 최소값은 2이고 최댓값은 8이다. 

 

따라서 기울기가 증가하는 대각선은 체크배열의 행+열 위치에 체크하여 기울기가 증가하는 대각선 상에 퀸을 

놓을 수 있는지 없는지를 쉽게 확인할 수 있다.

 

기울기가 감소하는 대각선도 아래와 같은 특징이 있다.

기울기가 감소하는 대각선 부분은 행과 열의 차가 일정하다. 범위는 n이 4일 경우 –3에서 3까지의 값을 지닌다. 음의 값을 양의 값으로 보정하기 위해 n을 더해주어 체크배열의 n+(행-열)의 위치에 체크하여, 퀸이 놓일 수 있는지 여부를 확인할 수 있다.

 

백트랙

백트랙 시에 가장 중요한 점은 체크배열에 기록해 두었던 체크를 모두 해제해야 한다는 점이다. 
비선형구조의 탐색에서 복귀 시에 흔적을 지우는 것은 매우 중요한 요소이므로 익힐 수 있도록 한다.

 

 

깊이우선탐색을 기반으로 퀸을 더 이상 못 놓는 상태라면 이전 상태로 백트랙하여 가능한 상태가 될 때까지 반복하는 것을 구현한 것이다.

 

key

• 알고리즘의 효율을 높이기 위하여 퀸을 놓을 수 있는지 없는지를 O(1)만에 계산하기 위해, 현재 상태를 col, inc, dec라는 3개의 배열에 각각 열, 대각선 2가지의 상태를 저장하여 매우 빠른 속도로 처리할 수 있도록 하였다.

 

r => row 행을 나타내는 변수

row는 이미 다음 row로 넘어왔으므로 이전의 row는 고려하지 않는다.