[BOJ] 9663:N-queen

0. 문제

https://www.acmicpc.net/problem/9663

9663번: N-Queen

1. 문제분석

-  N개의 퀸을 체스판에 배치하는 모든 경우의 수에 대해 판단해야 하므로 Brute Force방식으로 각 좌표에 queen이 있는 상황을 다 따져보아야 한다.

- N개의 queen이 있는 상황에 대해 조건 만족을 판단하기 위해 체스판을 설정한 뒤에는, 다시 또 다른 경우의 수를 판단하기 위해 체스판의 설정을 되돌려놓은 후 다른 경우의 수를 탐색해야 한다. 따라서 BackTracking 알고리즘을 사용해야 한다.

 

2. 주의할 점

- 모든 체스판 좌표에 대해서 boolean 값을 갖는 이차원 배열을 만들어 문제를 푸는 방식은 문제를 해결하기에는 시간이 부족하다.

- 퀸의 움직임 특성 상, 현재 좌표를 기준으로 같은 행, 같은 열, 같은 좌상향 대각선, 같은 우상향 대각선에 있는 좌표들을 파악하고 각각의 선(행,열,대각선)에 있는 점들 간의 공통점을 찾아내야 한다.

- 행 또는 열 중 하나를 기준으로 잡고, 다른 조건을 만족하는지를 파악해야 한다. 어차피 어떤 행이나 열에 퀸이 존재한다면, 같은 행이나 열에는 다른 퀸을 놓을 수 없기 때문에 행 또는 열만 순차적으로 이동하면서 기준으로 삼으면서 문제를 풀면 문제가 훨씬 쉬워진다.

3. 소스코드(Java)

// boj 9663 : N-queen
// brute force, backtracking

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_09663 {
    static int N;
    static int ans;
    static final int MAX = 14;
    static boolean[] columnBlocked;
    static boolean[] rightUpBlocked;    // 우상향 대각선. 같은 대각선에 있는 좌표의 x-y값이 항상 같다.
    static boolean[] leftUpBlocked;     // 좌상향 대각선. 같은 대각선에 있는 좌표의 x+y값이 항상 같다.
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        columnBlocked = new boolean [N];
        rightUpBlocked = new boolean [2*N - 1 + MAX];
        leftUpBlocked = new boolean [2*N - 1];
        go(0);
        System.out.print(ans);
    }

    // row를 기준으로 잡으면, 모든 row를 순차적으로 다 돌고 마지막 row로 갔을 때 N개의 킌을 둔 것이 됨.
    // col에 대해서는 다른 row에서 어떤 col에 퀸을 뒀으면 그 col에는 퀸을 둘 수 없음.
    // 마찬가지로 우상향, 좌상향 대각선 상에 있는 좌표 중 하나에 퀸을 두었으면 해당 대각선에 포함되는 좌표에는 퀸을 둘 수 없음.
    static void go(int row) {
        if (row >= N) {
            ans++;
            return;
        }
        for (int col = 0; col < N; ++col) {
            if (columnBlocked[col] || rightUpBlocked[col - row + MAX] || leftUpBlocked[col+row]) continue;
            columnBlocked[col] = rightUpBlocked[col - row + MAX] = leftUpBlocked[col+row] = true;
            go(row + 1);
            columnBlocked[col] = rightUpBlocked[col - row + MAX] = leftUpBlocked[col+row] = false;
        }

    }

}

4. 여담

- 고전적인 문제이지만 역시 어렵다. 분명 전에 풀었었는데 기억이 잘안난다.ㅎ