N-Queens Problem (BOJ_9663)

N-Queens Problem 이란?

 

- N개의 Queen이 서로 상대방을 공격하지 않도록 NxN 체스판에 위치시키는 문제

  (Queen은 왼쪽,오른쪽,위,아래,대각선의 모든 방향으로 원하는 만큼 이동할 수 있다.)

 

- 서로 공격하지 않기 위해서는 : 같은 행 or 열 or 대각선 상에 위치하지 않아야 한다.

 

- 백트래킹(Back Tracking) 대표 문제

 

 

 

 

예) N=4일 때, 4-Queens 문제 해결 과정 

 

(1,1)~(4,4) 의 모든 위치를 탐색하며 퀸의 위치를 결정하는 DFS를 이용하면,

각 행마다 4가지의 경우를 각각 확인해야 하므로 4x4x4x4=256 가지의 경우를 탐색해야 한다.

 

모든 경우를 탐색해 결과를 찾아야 하기때문에 비효율적이므로,

각 행마다 퀸의 위치로 불가능한 위치는 탐색하지 않고, (non-promising 은 가지치기)

가능한 위치에서만 모든 경우를 탐색하는 방법인 백트래킹을 이용한다.

 

 

 

 

 

 

4-Queens problem - 해결 과정

 

 

 

 

 

해결 방법은 다음과 같다.

 

1. (1,1)~(4,4) 까지의 모든 가지를 나타내는 상태공간트리를 이용해 깊이우선탐색(DFS)를 실시한다.

     첫 번째 행에서 퀸을 1열부터 차례대로 넣고, 그 다음 행에서 퀸을 넣으며 차례대로 탐색한다.

 

2. 각 노드가 퀸의 위치로 가능한 지를 확인한다. ('유망한' 노드 찾기)

    모든 노드가 같은 행 or 열 or 대각선 상에 위치하지 않는다면, 퀸을 넣을 수 있다. (퀸의 위치로 가능하다.)

 

3. 만약 그 노드가 퀸의 위치로 불가능하다면 (= 같은 행/열/대각선 상에 있다면)

    그 노드의 부모노드로 돌아가서 탐색을 계속한다.

 

 

 

 

 

확장해서 N-Queens Problem 해결해보자!

 

4-Queens Problem에서 본 것과 같이, 각 행마다 '유망한' 노드를 찾으며 문제를 해결한다.

 

 

문제 해결방법은 크게 보면 다음과 같다.

 

1. 0행 1열~n-1열에 각각 퀸이 위치한 경우, 1행~n-1행까지 dfs로 탐색하며 퀸이 위치할 수 있는 곳을 탐색한다.    

2. x번째 행에서, 퀸의 위치를 결정하기 위해서 - 같은 열/대각선 상에  퀸이 위치해있는 지를 확인한다.

 

 

 

 

- 각 행에 1개의 퀸이 위치한다는 걸 가정한다.

  체스판은 nXn 이므로, 각 행마다 1개의 퀸이 위치하면 총 n개의 퀸이 위치하는 걸 의미한다.

 

  그러므로 퀸이 0행0열에 위치한 경우, 1행에 몇 번째 열에 위치할 수 있는지 탐색하고,

  만약 1행에 위치할 수 있는 곳이 없다면, 0행0열 -> 0행1열로 퀸의 위치를 바꾸어 다시 탐색한다.

  만약 1행에 위치할 수 있는 곳이 있다면, 계속해서 2행에 퀸이 위치할 수 있는 곳을 탐색한다.

 

  위와 같이, 퀸이 0행0열, 0행1열, 0행2열, ... 0행n-1열에 각각 위치했을 때

  1행,2행,... n-1행까지 모든 행에서 '퀸이 위치할 수 있는 열의 위치'를 찾는다.

 

 x행에 있는 퀸의 열 번호(위치)y 는 col[x]=y 로 표현하고, 이는 x행y열에 퀸이 위치함을 의미한다.

 

 

 

- 각 행에서 퀸이 위치할 수 있는 열의 위치를 찾기 위해서, 다음의 조건으로 판단한다.

 

   우리가 고려해야하는 건 두 가지이다.

   1. 같은 열 상에 두 개의 퀸이 위치해 있는가?

   2. 같은 대각선 상에 두 개의 퀸이 위치해 있는가?

 

☞  위에서 얘기한 것처럼 i번째 행에 퀸이 위치한 열을 col[i] 로 나타내어 조건식을 표현하면,

 

1. 같은 열 상에 두 개의 퀸이 위치해 있는가?

     if (col(i) == col(j)) 이면 불가능한 경우 (non-promising)

 

2. 같은 대각선 상에 두 개의 퀸이 위치해 있는가?

    if(abs(col(i)-col(j)) == abs(i-j))  이면 불가능한 경우 (non-promising)

 

 

 

 

 

코드 구현 (백준 9663번)

import java.util.Scanner;

public class Main {
    static int n;
    static int ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for(int i=0; i<n; i++){
            int[] col = new int[n]; // col[i]=j == i행j열에 퀸이 위치함 을 의미한다.

            col[0] = i; //0행0열 ~ 0행n-1열 까지 퀸이 위치했을 때,
            dfs(col, 0); //나머지 행에서 퀸이 위치할 수 있는 곳 찾기 (dfs로 탐색)
        }

        System.out.println(ans);
    }

    private static void dfs(int[] col, int row){ //다음 행에서의 퀸의 위치 탐색(1~n-1행까지 탐색)
        if(row == n-1){ //n-1행까지 탐색했을 때 == 모든 행에서 퀸이 위치할 수 있는 곳 찾음 을 의미
            ans++;
            return;
        }

        for(int i=0; i<n; i++){
            col[row+1] = i; //다음 행에서 퀸의 위치 0열~n-1열 까지 설정한 후,
            if(promising(col, row+1)) //그곳에 퀸 넣을 수 있는 지 확인
                dfs(col,row+1); //만약 그곳에 퀸 넣을 수 있다면, 그 다음행에서의 퀸의 위치 탐색
        }
    }

    private static boolean promising(int[] col, int row){ //해당 열(위치)에 퀸을 놓을 수 있는 지 확인
        for(int i=0; i<row; i++){ //같은 열or대각선 상에 퀸이 위치 -> 불가능
            if(col[i]==col[row] || Math.abs(col[i]-col[row])==Math.abs(i-row))
                return false;
        }
        return true;
    }
}

 

9663번: N-Queen