NQueen

NQueen 문제

---

전형적인 DFS 문제다.

놓을 수 있는 자리에 퀸을 놓고 그 다음 자리(다음 row 혹은 다음 col) 에 퀸을 놓을 수 있는지, 재귀로 확인한다.

N*N 보드에는 무조건 N개의 퀸이 와야 하는데, 그러려면 한 줄 (row 는 물론이고 col) 에 무조건 퀸이 하나 있어야 한다.

그러니, 즉 줄 단위로 확인해 가면서 퀸을 놓는지 확인하고, 놓을 수 있다면 그 다음 줄로 넘어가는 DFS 인 것이다.

물론 모든 칸을 다 확인해가면서 자리를 찾을 필요는 없고, 퀸이 절대로 있을 수 없는 자리를 가지치기 하면 된다.

퀸은 다른 퀸이 있는 자리에서 세로/가로/좌 대각선/우 대각선에 해당 하는 곳은 위치할 수 없다.

그러니, 처음에 퀸이 있을 수 있는 자리에 임의의 값 1을 대입하고, 그 다음 줄로 넘어가면서 퀸이 있을 수 있는 자리를 찾을 때, 그 지점의 세로/가로/좌 대각선/우 대각선에 1이 있는지만 확인하면 된다.

만약 값 1이 있다면 해당 지점엔 퀸이 올 수 없으니, 그냥 넘어가고 가지 치기가 되지 않았다면 1로 값을 채워준다. 여기서, 값 1을 채워주고 DFS 를 다 돌았다면 다시 0으로 초기화 해주는 것을 잊지 말아야 한다.

처음에 대각선에 1이 있는 값을 찾을 때 절대 값으로 찾으려다가, 구현에서 틀려서 답이 나오지 않아, 그냥 해답을 보았다.

NQueen 문제는 유명해서 왠만한 OJ 사이트에는 다 있는 것 같다.

비슷하면서도 조금 다른 문제들이니 나중에 한 번 답 안 보고 처음 부터 다시 해봐야겠다. 

아래 코드는 알고스팟에서 통과되는 코드이다.

import java.util.Scanner;


public class NQueen {

    public boolean canPutQueen(int[][] board, int r, int c) {

        for (int p = 0; p < c; ++p) {
            if (board[r][p] == 1) {
                return false;
            }
        }

        int i, j;
        for (i = r, j = c; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        for (i = r, j = c; j >= 0 && i < board.length; i++, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        return true;
    }

    public int dfs(int[][] board, int col) {

        if (col >= board.length) {
            return 1;
        }

        int ret = 0;
        for (int row = 0; row < board.length; row++) {
            if (this.canPutQueen(board, row, col)) {
                board[row][col] = 1;
                ret += this.dfs(board, col + 1);
                board[row][col] = 0;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        NQueen main = new NQueen();

        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt();
        while (cases > 0) {
            cases -= 1;
            int boardSize = sc.nextInt();
            int[][] board = new int[boardSize][boardSize];
            System.out.println(main.dfs(board, 0));
        }
    }
}

NQueen 문제 리스트

• https://algospot.com/judge/problem/read/NQUEEN
• https://www.acmicpc.net/problem/9663
• https://leetcode.com/problems/n-queens/
• https://www.codechef.com/problems/TIC04