BOJ_9663_N-Queen 두기

이번 N_Queen 문제에서는 BFS의 심화버전인 Back Tracking, 다른 말로 퇴각검색법에 대해서 알아볼 것입니다.

[문제] 

N-Queen 문제를 해석하는 데에도 저는 조금 오래 걸렸습니다.

체스를 어릴 때 해보고 안해봐서도 있지만 생각을 어떻게 다르게 하느냐에 대해서도 고민이 많았기 때문입니다.

기존 풀이 방법은 앞서 설명한 대로

Queue를 만들고 Queue에서 맨 앞에 있는 것을 빼가면서 큐가 비어 있지 않다면 계속해서 반복문을 돌리도록 구현하였습니다.

또한 이미 지나간 곳이라면 boolean 배열의 값을 true로 주어서 다음에는 해당 노드를 방문하지 않도록 만들었고,

이동하면서 dist라는 배열로 해당 노드에서 다음 노드로 이동할 때 +1을 해주면서 값을 관리하였습니다.

BFS 문제가 다음과 같은 boolean 배열이나 값을 계산하는 dist 배열을 만들 필요는 없지만 구조는 비슷하게 진행됩니다.

예를 들어, boolean 배열이 아닌 연산 결과에 대해 boolean 값을 반환해주는 함수를 만들고,

dist배열 대신에 count 변수를 두어서 재귀함수로 계속해서 더해주어 count를 반환해줘도 됩니다.

따라서 N-Queen 문제를 확인하면 퀸의 공격 경로가 상하,좌우,양 대각선인데, 

한 행에는 각 열이 독립적으로 존재하기 때문에,

좌우는 체크할 필요가 없습니다.

그렇다면 상하,양 대각선만 체크하면 되는데, 체크라는 것이 어떤 의미냐면 

가령 1행 1열에 퀸이 있다면 해당 1열은 퀸이 오면 안됩니다. 

따라서 해당 col(열) 에 대해서는 이미 방문하였다는 값을 주고 다음 행으로 넘어가야 합니다.

마찬가지로 해당 열에 대해서 이미 방문하였다고 체크를 했다면 양 대각선에 대해서도 이미 방문하였다고

체크를 한 뒤에 다음 행으로 넘어가도록 구현해야 합니다.

다음 행으로 넘어는 부분에 있어서는 원래 같다면 이동 전의 노드의 값을 큐에 넣어주고, 

dist[next] = dist[now] + 1 ; 

이런 구조로 이동을 하나씩 증가시켰을 것이다.

이러한 구조와 비슷한 방법으로 재귀함수를 두어 count의 변수에 해당 함수의 반환된 값을 계속해서 더해주면서

반복문을 돌리면 전체 원하는 값이 나올 것 입니다. 

추가로 핵심 포인트 하나 더 말씀드리면 2차원 배열 문제가 나온다면 1차원 배열로 만드는 것이 중요하다

예를 들어, 한 행과 열에 대해서 퀸이 자리를 잡고 있다면, 해당 행과 열을 기준으로 양 대각선과 열에는 퀸이 올 수 없다.

이를 check_dv1[row][col] 로 계산해도 되지만 많이 복잡해진다.

따라서 check_dv1[___] 이렇게 1차원 배열로 만들어서 구현해야 하는데, 이 부분은 센스가 필요하다.

어떻게 2차원 배열을 1차원 배열로 만들까부터 생각해서 규칙을 만들어 내야 하는데,

한 열에 대해서 체크하는 배열은 행을 생각 안하고 열만 가지고 체크하기 때문에 1차원 배열로 진행하지만,

양 대각선은 연산이 필요하다.

양 대각선에 대해서는 다음과 같은 방식이 있다.

1번 대각선 방식은 row - col + 전체 갯수 (행)

2번 대각선 방식은 row + col 방식으로 생각해주면 된다.

1번 방식을 좀 더 구체적으로 설명하자면 (1,1) = 0 인데, 

이는 0-0+4 이고, (2,4) = 2 인데, 이는 2-4+4와 같다.

2번 대각선 방식은 (2,3) = 5 인데, 이는 2+3과 같고,

(4,2) = 6인데, 이는 4+2와 같다.

이렇게 행과 열 그리고 전체 갯수(행)만을 가지고 하나의 1차원 boolean 배열로 구현할 수 있다.

이렇게 구현한 체크 함수는 다음과 같다.

---

private static boolean check(int row, int col) {

if (check_col[col]) {

return false; // 처음값은 다 false로 초기화 된 상황

// 해당 열에 이미 퀸이 있다면 다음 열부터는 퀸이 올 수 없음

}

if (check_dv1[row + col]) {

return false;

}

if (check_dv2[row - col + row_num]) {

return false;

}

return true;

}

---

이제 퀸을 두는 함수를 만들어야 하는데, 여기서 중요한 것은 퀸을 둘 떄 Back-Tracking 방식을 사용해서 둔다는 것이다.

이는 기존 BFS방법과 조금 다른 방법으로, 이미 지나 온 곳이 다음 행에 대해서 반복문을 돌 때에는

원래 상태로 회귀해야 하므로 지나 온 곳을 모두 false로 돌려줘야 한다.

수식은 다음과 같다.

---

private static int queen_located(int row) {

if (row == row_num)

return 1;

int count = 0;

for (int col = 0; col < row_num; col++) {

if (check(row, col)) {

check_col[col] = true;

check_dv1[row + col] = true;

check_dv2[row - col + row_num] = true;

a[row][col] = true; // 퀸이 있움

count += queen_located(row + 1); // 다음 행으로 이동

// Back Tracking ... 다시 처음으로 돌린 다음에 행열 정리

//System.out.println("루프 체크" + " " + count);

check_col[col] = false;

check_dv1[row + col] = false;

check_dv2[row - col + row_num] = false;

a[row][col] = false;

}

}

return count;

}

---

전체 코드는 다음과 같다.

---

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class N_Queen {

static Scanner scanner;

static Queue queue;

static boolean a[][];

static int row_num;

static boolean check_dv1[];

static boolean check_dv2[];

static boolean check_col[];

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

queue = new LinkedList<Integer>();

row_num = scanner.nextInt();

a = new boolean[15][15]; // 행의 수가 10이면 10 * 10 행렬 만들어두기

// 행의 갯수

check_dv1 = new boolean[40];

check_dv2 = new boolean[40];

check_col = new boolean[row_num];

int ans = queen_located(0);

System.out.println(ans);

}

private static boolean check(int row, int col) {

if (check_col[col]) {

return false; // 처음값은 다 false로 초기화 된 상황

// 해당 열에 이미 퀸이 있다면 다음 열부터는 퀸이 올 수 없음

}

if (check_dv1[row + col]) {

return false;

}

if (check_dv2[row - col + row_num]) {

return false;

}

return true;

}

private static int queen_located(int row) {

if (row == row_num)

return 1;

int count = 0;

for (int col = 0; col < row_num; col++) {

if (check(row, col)) {

check_col[col] = true;

check_dv1[row + col] = true;

check_dv2[row - col + row_num] = true;

a[row][col] = true; // 퀸이 있움

count += queen_located(row + 1); // 다음 행으로 이동

// Back Tracking ... 다시 처음으로 돌린 다음에 행열 정리

//System.out.println("루프 체크" + " " + count);

check_col[col] = false;

check_dv1[row + col] = false;

check_dv2[row - col + row_num] = false;

a[row][col] = false;

}

}

return count;

}

}

---

점점 쉽지 않지만 방식을 이해하고 계속해서 그 방식에 맞게만 구현하면 된다.

뭔가 타이트하게 생각해서 정리하고 코드를 짜면 오히려 더 안풀리고 복잡해지는 것 같다.

기존에 방식을 유지한 채로 "이렇게 해볼까?" 라는 생각을 더하여 코드를 정리한다면 

타이트하게 하나하나 체크하면서 짜는 것 보다 더 정답에 가까운 코드를 짤 수 있을 것이다.