백준 9663번 : N-Queen java

이 문제는 N x N 사이즈의 체스판에 서로 공격하지 않게 퀸을 몇 개 놓을 수 있는지를 구하는 문제입니다.

출처 : 위키백과

 

퀸이 이동할 수 있는 공간은 위에 보이는 것과 같이 상 하 좌 우 각 방향의 대각선입니다.

이 문제를 풀기 위해서 퀸이 체스판의 어디 어디에 들어갈 수 있는지를 N이 4일 때를 예시로 보여드리겠습니다.

 

 

 

 

다음과 같이 퀸이 위치해 있을 떄 하얀 점이 있는 곳은 퀸이 갈 수 없습니다.

 

 

 

 

 

 

1열에 퀸이 왔으니 2열에 이제 새로운 퀸을 
추가하고 퀸이 위치할 수 없는 위치를 흰 점으로
표시합니다.

 

 

 

 

 

 

 

다음 3열에 들어갈 수 있는 위치는 1개이니 그 
자리에 퀸을 넣어줍니다.

 

 

 

 

 

 

 

이제 마지막 퀸까지 넣어주면 완성입니다.

 

 

 

 

 

이런 식으로 퀸이 들어갈 수 있는 자리들을 조건에 맞추어 찾으면 이 문제를 해결할 수 있습니다.

---

import java.io.*;

public class Main{
    static int cnt = 0;
    static int N;
    //여왕이 있는 자리를 나타내는 배열
    //안에 들어가 있는 수는 column이고 각 자리는 row를 의미
    static int[] queen;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        queen = new int[N];

        dfs(0);

        System.out.println(cnt);
    }

    static void dfs(int depth){
        if(depth == N){
            cnt++;
            return;
        }

        for(int i = 0; i<N; i++){
            queen[depth] = i;

            if(canPut(depth))
                dfs(depth+1);
        }
    }

    //여왕이 자리에 들어갈 수 있는지를 판단하는 함수
    static boolean canPut(int depth){
        for(int i = 0; i<depth; i++){
            if(queen[depth] == queen[i])
                return false;
    //row의 차이와 column의 차이가 같다면 대각선에 있다.
            else if(Math.abs(depth-i) == Math.abs(queen[depth] - queen[i]))
                return false;
        }
        return true;
    }
}

다음 코드블럭을 보시면 1차원 배열로 퀸이 어디 들어가 있는지 표현한 것을 보실 수 있습니다. 1차원 배열로 퀸의 위치를 표시한 이유는 배열의 0번 인덱스는 0번째 줄 1번 인덱스는 1번째 줄로 두면 문제를 메모리를 낭비하지 않고 풀 수 있기 때문입니다.

이렇게 1차원 배열로 두면 위에 예시를 들어 설명한 글에서의 퀸의 위치는
queen[0] = 1,  queen[1] = 3, queen[2] = 0, queen[3] = 2
이렇게 표현할 수 있습니다.

이렇게 값을 넣은 배열을 이용하여 canPut함수로 퀸이 들어갈 수 있는지를 확인하고 재귀를 이용하여 문제를 해결할 수 있습니다.