문제 바로가기

나의 풀이

visited[][] 배열을 사용해서 행, 열, 대각선에 대해 모두 방문 체크를 하는 백트래킹을 구현해봤으나 직전에 방문체크했던 곳을 해제하는 과정이 쉽지 않아 결국 구글링을 해봤습니다.

구글링으로 나온 결과에서는 대부분 1열, 2열, .. 순서로 퀸을 놓았는데 저는 직관적으로 1행, 2행, ... 순서로 퀸을 놓는게 더 이해하기 쉽다고 생각해서 그렇게 코드를 작성했습니다.

나의 코드

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

class Main {

    static int n ,count;
    static int[] chessMap;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        chessMap = new int[n];
        count = 0;

        nQueen(0);

        System.out.println(count);
    }

    private static void nQueen(int row) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            chessMap[row] = col;
            if (possible(row)) {
                nQueen(row + 1);
            }
        }
    }

    private static boolean possible(int row) {
        for (int i = 0; i < row; i++) {
            if (chessMap[row] == chessMap[i]) {
                return false;
            } else if (Math.abs(row - i) == Math.abs(chessMap[row] - chessMap[i])) {
                return false;
            }
        }
        return true;
    }
}