[BOJ] 9663 - (N-Queen)(G4)

문제 링크

9663-(N-Queen)

입력

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

출력

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

문제 풀이

이 문제를 풀기전에 제일 먼저 알아야하는 것은
퀸은 왼쪽, 오른쪽, 위, 아래, 대각선으로 이동이 가능하다는 것

즉, 퀸의 위치에서 위의 위치들을 재귀적으로 확인해야한다.

같은 행 또는 열에 위치하는지, 대각선에 위치하는지를 확인하는 check 함수와
재귀적으로 파악하는 nQueen 함수로 코드를 구성

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

public class Main {

    static int N, cnt = 0;
    static int[] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        map = new int[N];

        nQueen(0);
        System.out.println(cnt);
    }

    static void nQueen(int depth) {
        if (depth == N) {
            cnt++;
        } else {
            for (int i = 0; i < N; i++) {
                map[depth] = i;
                
                // 이동 가능 여부를 파악하여 백트랙킹 기법 사용
                // 재귀호출 사용
                if (check(depth)) {
                    nQueen(depth + 1);
                }
            }
        }

    }
    static boolean check(int depth) {
        for (int i = 0; i < depth; i++) {
        
        	// 같은 행에 존재하는지
            if (map[i] == map[depth]) {
                return false;
            }
            
            // 대각선에 존재하는지
            if (Math.abs(i - depth) == Math.abs(map[i] - map[depth])) {
                return false;
            }
        }
        return true;
    }
}