N_Queen

오늘은 N_Queen 문제를 체크해보려합니다.

가장 대표적인 재귀형 문제이자, 백트래킹의 개념이 들어간 문제이기도 합니다.

우선 N_Queen의 조건을 체크해봅시다.

---

조건1. 각 행에는 퀸을 중복해서 둘 수 없다.

조건2. 각 열에는 퀸을 중복해서 둘 수 없다.

조건3. 각 대각선 (사선 두 방향)은 퀸을 중복해서 둘 수 없다.

---

함수를 만들때 열에 대해서 n번의 재귀를 통해서 반복하는 함수를 만든다.

이 함수 안에서는 n-1번째 열에 대해서 행이 0부터 n-1번째까지 반복을 통해 체크하도록 한다.

이렇게하면 결국 행과 열 모두 다 도는 것과 마찬가지다.

단! 조건1과 조건2를 만족시키기 위해서는 반복을 돌 때 재귀를 통해 열에 대해서 0행에 모두 퀸을 배치시킬 경우,

다음 열에 대해서는 0행이 아닌 다른 곳에 퀸을 배치하는 조건을 둡니다.

마찬가지로, 대각선 (각 사선(2방향)) 모두 조건을 두어 작업합니다.

---

private static void set(int x){ //  x 좌표 --> 열

for(int i=0;i<n;i++){

if(flag[i] == false){ // 한 열에 대해서 행 체크 --> 퀸 두는 곳 (아직 안두었다면)

pos[x] = i; // x열에 대해서 행 i를 넣어주기 

if(i==n-1){

// 마지막 행에 도달할 경우 

printSet(); // 

} else {

flag[i] = true; // 행 방문 완료

set(x+1); // 재귀로 먼저 열 체크해주면서 확인 --> 행은 이미 0행부터 싸그리 방문한 상태 

flag[i] = false; 

// 다음 열 돌 땐 행 하나가 방문하지 않은 상태로 둔 다음에 변화를 주면서 방문하기 >> 재귀 호출이 끝나면 

// 호출 전 상태로 다시 돌아감과 같은 이치

}

}

}

}

---

여기는 N_ROOK와 같다. 

하지만 Queen은 대각선도 포함해야한다.

대각선을 둘 때에는 두가지 길이 있는데 인덱스간 차이를 잘 체크해야한다.

이해가 어렵다면, 3*3 퀸을 만들어서 대각선 인덱스가 어떻게 들어갈 것인지 먼저 체크하고 

코드를 정리하는 것이 낫다.

아래 그림을 참조하자

대각선에서 방문 체크하는 배열은 다음과 같이 둘 수 있습니다.

이를 코드에 추가하면 됩니다.

마찬가지로 조건3을 그대로 구현하는 것과 같습니다.

전체 코드는 아래와 같습니다.

앞서 조건1,조건2로만 정의되었던 코드에 대각선에 퀸을 제한하는 조건도 확인하시기 바랍니다.

[전체코드]

---

public class N_Queen_8 {

private static int[] pos;

private static boolean[] flag;

private static boolean[] flag_dir1; // 대각선1

private static boolean[] flag_dir2; // 대각선2

public static void main(String[] args) {

// TODO Auto-generated method stub

pos = new int[8];

flag = new boolean[8];

flag_dir1 = new boolean[15];

flag_dir2 = new boolean[15];

set(0);

}

/*

* 8퀸 문제 조건1. 행에 퀸이 겹치지 않게 둔다. 조건2. 열에 퀸이 겹치지 않게 둔다. 조건3. 대각선에 퀸이 겹치지 않게 둔다.

* 

* --> 조건1과2를 만족하기 위해서는 1차원 배열이 필요하고 해당 행에 퀸을 두었는지 체크하는 것이 필요합니다. pos[i] = j 라고

* 한다면, i열에 j행(퀸)을 둔 것이라 할 수 있습니다. i는 8열까지 이므로 8번 돌리고 j행 또한 8번 돌립니다. 단, 열에 대해서

* 행에 퀸을 둘 때 해당 행에 퀸이 두어진 상황이라면, 다음 행에는 두지 않도록 구현합니다. 마찬가지로 열로 넘어갈 때에도 해당 열에 퀸이

* 겹치지 않도록 구현합니다.

*/

static void set(int j) {

// j열

for (int i = 0; i < 8; i++) {

// 행 진행

// 여기다가 대각선도 추가

if (flag[i] == false && flag_dir1[j + i] == false && flag_dir2[j - i + 7] == false) {

// 해당 행에 대해서 퀸을 두지 않았을 경우 --> 행==퀸 (다음 행에 두지 않도록 구현)

pos[j] = i; // j열에 대해서 행에 퀸 두기 시작 --> 행도 겹치지 않게 구현하면서 열도 겹치지 않게 구현

if (i == 7) {

// 마지막일때 결과 출력

printSet();

} else {

flag[i] = true; // 행 방문 완료

flag_dir1[j + i] = true;

flag_dir2[j - i + 7] = true;

set(j + 1);

flag[i] = false; // 행 싹다 비교하고 나서 (for문 다 돈 것) 다시 돌아와서는 열 돌릴 때 처음부터 방문 다시 시작

flag_dir1[j + i] = false;

flag_dir2[j - i + 7] = false;

}

}

}

}

private static void printSet() {

// TODO Auto-generated method stub

for (int i = 0; i < 8; i++) {

System.out.print(pos[i] + " ");

}

System.out.println("");

}

}

---

감사합니다.