알고리즘 풀이 - 백준 9663(N-Queen, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

N-Queen 문제로 NxN 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제

 

 

2. 풀이

 

유명한 N-Queen 문제이다. NxN 체스판에 가능한 모든 경우에 퀸의 위치를 검사해 그 경우가 서로를 공격할 수 있는 위치라면 위치시키지 않고 가능한 경우만 체크하여 모든 경우의 수를 구하는 문제이다.

재귀로 간단히 풀 수 있다. 체크해보자.

① 체스판의 크기를 입력받아 그 크기에 맞은 2차원 배열을 생성한다.
② (0, 0) 부터 시작하여 퀸을 위치시키도록 재귀함수에 현재 퀸을 위치시킬 Column 번호를 전달하여 시작한다.
③ 현재 Column에서 각 Row를 체크하여 퀸을 위치시킬 수 있다면 위치시키고 다음 Column으로 넘어간다.
④ 현재 Column 번호가 N이 되는 순간은 모든 퀸이 위치한 것이므로 경우의 수를 +1 해준다.

 

각 열을 기준으로 퀸을 위치시킬 수 있는지 조사하는 문제이므로 현재 열을 기준 이전 열의 대각선(좌상, 좌하) 또는 같은 행의 위치에 퀸이 이미 위치해 있는지 조사하여 새로운 퀸의 적절한 위치를 구한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;
import java.util.*;

public class Main{
    static int n;
    static int[][] chess;
    static int ans = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        chess = new int[n][n];
        
        bruteForce(0);
        System.out.println(ans);
        br.close();
    }
    
    private static void bruteForce(int col){
        if(col >= n) {
            ans++; return;
        }
        
        for(int i=0; i < n; i++){
            // 퀸을 현재 위치에 놓는 것이 가능한 경우에만 위치한다.
            if(check(i, col)){
                chess[i][col] = 1;
                // 다음 열로 넘어간다.
                bruteForce(col+1);
                chess[i][col] = 0;
            }
        }
    }
    
    // 퀸을 위치시킬 수 있는지 체크하는 메소드
    private static boolean check(int row, int col){
        int i, j;
        
        // 같은 row에 이미 있으면 위치 불가
        for(i=0; i < col; i++){
            if(chess[row][i] == 1) return false;
        }
        
        // 이전 열의 좌상 대각선 방향으로 이미 위치 시 위치 불가
        for(i=row, j=col; i >= 0 && j >= 0; i--, j--){
            if(chess[i][j] == 1) return false;
        }
        
        // 이전 열의 좌하 대각선 방향으로 이미 위치 시 위치 불가
        for(i=row, j=col; i < n && j >= 0; i++, j--){
            if(chess[i][j] == 1) return false;
        }
        
        // 그 외의 경우에는 위치시킬 수 있음
        return true;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.