[JAVA] 백준 (골드4) 9663번 N-Queen

링크

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

---

문제 설명

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

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

---

입력 예제

• 첫째 줄에 N이 주어진다. (1 ≤ N < 15)

8

---

출력 예제

• 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

92

---

풀이

퀸은 상, 하, 좌, 우에 대각선까지 이동할 수 있으므로 각 행과 열에는 하나의 퀸만 올 수 있다. 그러므로 2차원 배열 대신에 1차원 배열로 구현할 수 있다. 가령 2행의 3열에 퀸이 있다면 board[2] = 3 이라고 표현 할 수 있다. 이렇게 하여 모든 행에 대하여 퀸을 놓을수 있다면 정답으로 카운트한다.

첫 번째 행부터 모든 열에 대해 반복하면서 퀸을 놓을 수 있으면 재귀를 호출한다. 재귀를 호출하면서 마지막 행까지 퀸을 놓을 수 있으면 한 번 더 재귀를 호출하고 반환한다.

static void backTracking(int row) {
    //각 행을 다 채우면 카운트 후 리턴
    if (row == N) {
        count++;
        return;
    }
    //모든 열에 대하여 반복
    for (int col = 0; col < N; col++) {
        board[row] = col;  //row행의 col열에 퀸을 놓음
        //해당 행에 놓을 수 있으면 재귀 호출
        if (possibility(row)) {
            backTracking(row + 1);
        }
    }
}

퀸을 놓을 수 있는지는 같은 열에 퀸이 존재하거나 대각선 상에 존재할 경우로 놓여있다고 판단한다. 대각선의 경우 변화량이 같으면 기울기가 1또는 -1으로 같은 대각선에 있다고 판단할 수 있다.

static boolean possibility(int row) {
    for (int i = 0; i < row; i++) {
        //row행에 i행과 같은 열에 존재할 경우
        if (board[i] == board[row]) {
            return false;
        }
        //대각선 상에 있는 경우
        else if (Math.abs(row - i) == Math.abs(board[row] - board[i])) {
            return false;
        }
    }
    return true;
}

코드

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

//백준
public class Main {

    static int N;
    static int count = 0;
    static int[] board;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        board = new int[N];

        backTracking(0);

        System.out.println(count);
    }

    static void backTracking(int row) {
        //각 행을 다 채우면 카운트 후 리턴
        if (row == N) {
            count++;
            return;
        }

        //모든 열에 대하여 반복
        for (int col = 0; col < N; col++) {
            board[row] = col;  //row행의 col열에 퀸을 놓음
            //해당 행에 놓을 수 있으면 재귀 호출
            if (possibility(row)) {
                backTracking(row + 1);
            }
        }
    }

    static boolean possibility(int row) {
        for (int i = 0; i < row; i++) {
            //row행에 i행과 같은 열에 존재할 경우
            if (board[i] == board[row]) {
                return false;
            }
            //대각선 상에 있는 경우
            else if (Math.abs(row - i) == Math.abs(board[row] - board[i])) {
                return false;
            }
        }
        return true;
    }
}