[백준] 9663. N-Queen / Java

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

9663번: N-Queen

---

문제 풀이

이 문제는 크기가 N * N인 체스판 위에 퀸 N 개를 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제이다.

기본적으로 BruteForce 유형이나 isPromising()과 같은 메서드를 활용하여 가망이 없는 경로를 가지치기 하며 진행하는 BackTracking 기법이 가미되어 있다.

 

우선 눈여겨 볼 점은 이 차원으로 이루어진 체스판을 일 차원 배열(board[])로 바꾸어 생각한다는 것이다.

배열의 인덱스는 행(row)이며 해당 인덱스에 들어있는 값은 열(col)이다.

예를 들어, board[0] = 1 이면, 1행 2열에 말이 놓여져 있음을 의미한다.

 

풀이의 흐름은 행을 기준으로 진행된다. 

첫 번째 행부터 시작해서 각 행의 모든 열에 말을 놓는 경우를 탐색한다.

특정 행(row)에 말을 놓았으면 isPromising()을 통해 지금까지 1행부터 row행까지 놓은 말의 위치가 서로를 공격하지 않는 위치에 놓여져 있는지 확인한다. 그 결과가 true이면 다음행으로의 탐색으로 이어지고 false이면 더 이상 진행되지 않음으로써 불필요한 계산을 줄일 수 있다.

소스 코드

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

public class BOJ9663 {

    static int N, cnt;
    static int[] board;
    
    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];
        cnt = 0;
        nQueen(0);

        System.out.println(cnt);
    }

    static void nQueen(int row) {
        // 가능한 경우 찾았을 때
        if (row == N) {
            cnt++;
            return;
        }

        // 첫 행의 1~N 번째에 놓는 모든 경우의 수를 탐색
        for (int i = 0; i < N; i++) {
            board[row] = i;
			
            // 첫 행부터 row 행까지 채워넣은 값이 유효한지 확인
            if (isPromising(row)) {
                nQueen(row+1);
            }
        }
    }

    static boolean isPromising(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;
    }
    
}