Yunseok Byeon

Yunseok Byeon

Motivational Speaker

백준 9663번 : N-Queen

1. 문제 설명 (9663)

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

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

2. 분류

3. 풀이

가장 유명한 Back-tracking 문제라고 한다. A4용지에 5 x 5 크기 까지의 체스판을 그려보면서 규칙성이 있나 찾아봤지만, 그런건 없었다. 단순히 생각해 보니 가로, 세로가 같은 숫자 일 경우와, 대각선일 경우 의 경우만 판별해 주면 됐다.

그래서 N x 1의 일차원 배열 을 활용해 풀이했다.

  1. 체스판을 나타내는 일차원 배열인 board[N] 을 만들었고, board[N] 은 퀸을 놓는 col 값을 의미한다.
  2. isPossible 메소드의 경우, 그 이전 row 값들 을 순차적으로 for loop를 통해 탐색하고, 해당 board[row]값 이 이전 board[N] 값들과 일치하는 경우와 대각선일 경우 false 를 return 한다.
  3. putQueen 메소드의 경우, 각 col 별로 한 번씩, 한 loop 당 N개의 col을 탐색 한다.
  4. row값이 N에 도달 하면 board[N-1]까지의 값이 모두 true 이므로, answer값을 1 추가한다.

4. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.io.*;
 
public class Q9663 {
    
    static int N;
    static int[] board;
    static int answer = 0;
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        N = Integer.parseInt(br.readLine());
        board = new int[N];
 
        putQueen(0);
        bw.write(answer+"");
        bw.flush();
        bw.close();
    }
    
    static boolean isPossible(int row) {
        for(int i = 0; i < row; i++) {
            if(board[i] == board[row] || (row - i) == Math.abs(board[i] - board[row]))
                return false;
        }
        return true;
    }
    
    static void putQueen(int row) {
        if(row >= N) {
            answer++;
            return;
        }
        
        for(int col = 0; col < N; col++) {
            board[row] = col;
            if(isPossible(row))
                putQueen(row+1);
        }
        
    }
}
 
cs


5. 결과

result image

4704ms로 잘 작동한다. Brute-force 문제 답게 엄청난 시간이 소요된다.

댓글남기기

참고