백준N-Queen_9663_백트레킹

-문제-

 

 

 

-문제 접근-

 

1. 문제 조건

• 위 문제는 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없도록 놓는 경우의 수를 구하는 문제입니다.
• 퀸이 놓여진 행과 열 그리고 대각선 방향에는 아무것도 놓여있으면 안되는 조건을 가지고 있습니다.

2. 문제 접근

• 문제를 처음 봤을 때는 NxN의 체스판이라 당연히 2차원 배열을 생각해보게 되지만 문제의 조건에 조금 더 생각해보면 "각 행에 하나의 퀸만 놓을 수 있다" 라는 조건이 있으므로 각 행에 대해 열 번호만 저장하면 체스판의 모든 좌표를 표현 할 수 있습니다. 
•  예시) n = 3 일때 board[0] =1 하면 0번째 행, 1번째 열에 퀸이 있다를 의미하게 됩니다.

 

• 문제 조건 적용을 하면 같은 열에 퀸이 위치 할 수 없기 때문에 board[0] = 0 이면  board[1] = 0 이 될 수 없다는 것을 알 수 있습니다. 그리고 board[0] = 0에 퀸이 위치해 있을 경우에 board[1] = 1에 위치 한다고 하면 열과 행은 문제가 되지 않지만 대각선 조건에 문제가 생깁니다. 위처럼 행과 열의 차가 같다면 퀸은 대각선 위치를 하므로 

1.  board[행] = 열 에서 열의 값이 같으면 안된다.
2. (행 - 행) = (열 - 열) 이라면 대각선에 위치한 것이므로 안된다. 

 

3. 구현

조건을 만족하는지 여부를 알아야되므로 bool 함수가 필요하며 위 조건들을 처리 해주어야 합니다.

 

각 행마다 퀸을 놓는 모든 가능한 경우를 시도하면서, 가능한 배치만을 유지하고 충돌이 있는 경우에는 즉시 되돌아가는 방식(백트래킹)으로 동작해야 합니다.

 

 

-코드-

 

-코드 설명-

 

• 같은 열 검사:
  if (board[cdx] == board[i])
  cdx번째 행의 퀸과 i번째 행의 퀸이 같은 열에 있으면, 같은 열에 있는 것이므로 충돌입니다.
• 대각선 검사:
  if (cdx - i == abs(board[cdx] - board[i]))
  두 퀸이 대각선 상에 있다는 조건은, 행 간의 차이와 열 간의 차이가 동일할 때 성립합니다.
  예를 들어 (3,1)과 (5,3)은 5−3=2이고,∣3−1∣=2이므로 같은 대각선상에 있습니다.
• 각 행에 대한 열 탐색:
  for 루프를 통해 현재 행의 0번부터 n−1번 열까지 하나씩 시도합니다.
  • board[cdx] = i;
    현재 행 cdx에 i번째 열에 퀸을 놓는 시도를 합니다.
  • if (promising(cdx))
    현재까지의 배치가 유효한지 검사합니다. 만약 같은 열이나 대각선에 다른 퀸이 있으면 배치가 무효하므로 다음 열을 시도합니다.
  • nqueen(cdx + 1);
    현재 행의 배치가 유망하면, 다음 행으로 진행하여 재귀 호출을 통해 배치를 이어갑니다.

 

 

-재귀 동작 이해-

입력: n=3

 

1. 0번째 행: nqueen(0)

• board[0] = 0
• promising(0)를 호출합니다.
• cdx=0인 경우, 비교할 이전 행이 없으므로 항상 true
• 재귀 호출:
  • 유망하므로 nqueen(1) 호출하여 1번째 행으로 진행합니다.

2. 1번째 행: nqueen(1) (현재 상태: board[0]=0)

• i = 0:  board[1] = 0 같은 열이므로 false
• i = 1: board[1] = 1은 행 - 행 = 열 - 열을 하면 값이 같으므로 대각선상에 있음 false
• i =2: board[1] = 2는 조건에 걸리는게 없으므로 true
• nqueen(2) 호출하여 2번째 행으로 진행.

2번째 행에서는 어떠한 i값도 성립이 되지 않으므로 반환이 됩니다.

 

백트래킹 및 복귀 과정

• 2번째 행: 모든 i값에 대해 재귀 호출이 이루어지지 않았으므로, nqueen(2) 호출이 종료되고 제어는 1번째 행의 for 루프로 돌아갑니다.
• 1번째 행: i = 0 과 i = 1 에서 유망하지 않았고 i = 2 에서 재귀 호출을 했으나 결국 해를 찾지 못합니다.
• 0번째 행: 이후 0번째 행에서 i = 0으로 설정한 분기의 재귀가 모두 종료됩니다.

 

-총정리-

재귀 함수는 각 행에서 가능한 열을 하나씩 시도하고, 각 시도마다 유망성을 검사한 후 다음 행으로 재귀 호출하여 전체 경우의 수를 탐색합니다. 만약 유망하지 않다면 재귀 호출 없이 for 루프가 다음 열로 넘어갑니다.(백트래킹)