[백준/BOJ] 9663 N-Queen - JAVA

[백준/BOJ] 9663 N-Queen - JAVA

문제

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

 

문제 분석

조건

• `N×N` 체스판 위에 N개의 퀸을 서로 공격하지 못하도록 배치하는 경우의 수를 출력

풀이방법

체스에서 퀸은 가로, 세로, 대각선 방향으로 공격을 할 수 있다. 따라서 서로 공격하지 않으려면 한 행에 하나의 퀸만 존재하고, 같은 열과 대각선 방향에 다른 퀸이 존재하지 않아야 된다.

첫 번째 행부터 퀸의 위치가 1개 정해지면 다음 행에서는 다른 퀸이 존재할 수 있는 자리가 정해진다. 한 행마다 퀸을 한 개씩 놓는 방식으로 검사한다.

`setQueen`함수에서 해당 행에서 `col`열에 퀸을 배치하고 같은 열이나 대각선 방향에 다른 퀸이 없는지 확인한다. 유효성을 확인한 뒤 다음 행의 퀸을 설정하는 `setQueen`함수를 재귀호출한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] board; // board[row] = col
    static int N;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N];
        setQueen(0);
        System.out.println(answer);

    }

    private static void setQueen(int line) {       //놓으려고 하는 퀸의 행 번호
        if (line == N) {
            answer++;
            return;
        }

        for (int col = 0; col < N; col++) {
            board[line] = col; // 퀸을 놓고
            if (isAvailable(line)) {    // 놓은 퀸 위치가 유효한지 확인
                setQueen(line + 1); // 유효하다면 다음 행에 퀸 놓기
            }
        }
    }

    /**
     *  board[line] = col;을 대입한 상태에서 유효한 자리에 대입이 된 것인지 확인
     * @param line
     * @return
     */
    private static boolean isAvailable(int line) {
        for (int col = 0; col < line; col++) {
            if (board[col] == board[line]   // 이전 행에서 이미 같은 열에 놓은 퀸이 있는지 확인
                    || Math.abs(board[col] - board[line]) == line - col) {  // 대각선 확인(열의 차이가 행의 차이와 같다면 대각선임)
                return false;
            }
        }
        return true;
    }
}

+

싸피에서 풀이과정까지 들으며 신기했던 문제인데 다시 풀면서 풀이는 다 까먹고 DFS로 풀어서 메모리 초과를 경험했다. 중간에 메모리 초과하겠다는 생각은 들었는데 풀이는 생각나지 않았다. 제출했던 코드를 보니 다시 생각나긴 했지만 대각선을 확인하는 부분을 잘 기억해야겠다. 나중에 다시 풀 때 또 저 부분이 생각 안 날 거 같다.