[백준 알고리즘] 9663번 N-Queen

백준 알고리즘

N-Queen(9663번)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
10 초	128 MB	11561	6682	4325	57.767%

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1 복사

8

예제 출력 1 복사

92

이 문제는 완전탐색, 백트랙킹을 이용한 접근으로 풀이하였다. 기본 전략은 다음과 같다.

• row 0 부터 순차적으로 col을 선택한다.

• col 선택을 확정짓기전에 해당 col 인덱스에 놓아도 적합한지 검사한다. (check 함수를 통해)

• row를 1증가시켜 다음 행에서 마찬가지로 col을 움직이며 적합한 값을 찾아나간다.

• 탐색이 완료된 이후에는 다음 탐색을 위해 기존 true로 바꾸었던 인덱스의 값을 false로 바꿔준다. (백트랙킹)

import java.util.Scanner;
​
public class Question9663 {
    static int N;
    static boolean[][] chess;
    static int ans = 0;
​
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        chess = new boolean[N][N];
​
        solve(0);
        System.out.println(ans);
​
    }
​
    public static void solve(int row){
        if(row == N){
            ans++;
            return;
        }
​
        for(int i=0;i<N;i++){
            if(!check(row, i)) continue;
            chess[row][i] = true;
            solve(row+1);
            chess[row][i] = false;
        }
    }
​
    public static boolean check(int row, int col) {
​
        for(int i=row;i>=0;i--){ // 세로 줄 검사
            if(chess[i][col]) return false;
        }
​
        //왼쪽 대각선 검사
        int dx = -1;
        int dy = -1;
​
        int newRow = row+dx;
        int newCol = col+dy;
​
        while(newRow>=0 && newCol>= 0){
            if(chess[newRow--][newCol--] == true) return false;
        }
​
        //오른쪽 대각선 검사
        dx = -1;
        dy = 1;
​
        newRow = row+dx;
        newCol = col+dy;
​
        while(newRow>=0 && newCol< N){
            if(chess[newRow--][newCol++] == true) return false;
        }
​
        return true;
    }
}
​

check 함수의 대각선 검사 중 대각선의 특성(오른쪽이 위인 대각선의 기준에는 가로와 세로의 값의 합이 모두 동일하고, 왼쪽이 위에 있는 대각선의 기준에는 가로와 세로의 차이가 모두 동일하다)을 이용한 효율적인 작성이 가능하므로 적용해보아도 좋을 것 같다.