백트래킹

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

가로,세로, 대각선(오른쪽, 왼쪽)

발상의 전환 : 배열의 index를 열로 두고, 해당 index의 값을 행

• 분명 2차원 배열의 정사각형에서 퀸을 서로 공격할 수 없는 위치에 나열하는 것이 문제이다.
• 하지만, 생각해보면, 1차원 배열만을 가지고도 경우의 수는 계산할 수 있다.
  • 배열에서 index값을 열로 나타내고, index에 들어가있는 값을 행으로 표현하면 된다.
  • 예시로 들자면 N이 4일 때, [1, 2, 3, 4]의 경우에는 1열 1행에 퀸이 있다는 뜻이고, 2열 2행에 퀸이 있다는 의미에 해당한다.

col - i 는 열의 차가, arr[col] - arr[i]가 행의 차

index를 '열'이라 생각하고, 원소 값을 '행'이라 생각하라는 말 처럼 인덱스의 값이 행이 되고, 해당 행의 차를 구하는 것입니다.

👇 동영상 참고
https://www.youtube.com/watch?v=gcuZ_VGIcn4 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
https://www.acmicpc.net/problem/9663
백트래킹 14468KB 5296ms
*/
public class NQueen {
    public static int N;
    public static int[] board;
    static int count = 0;

    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());
        board = new int[N];
        dfs(0);
        System.out.println(count);
    }
    public static void dfs(int depth) { // depth=열
        if(depth == N) { // 모든 조건을 통과한 경우
            count++;
            return;
        }
        for (int i = 0; i < N; i++) {
            board[depth] = i; // 유망성 체크가 true일 경우, 가지치기를 하지 않고 계속해서 진행

            if(isPossibleCheck(depth))
                dfs(depth + 1); // 다음 자식 노드 방문을 위해 depth 1 증가시키면서 재귀호출
        }
    }
    public static boolean isPossibleCheck(int column) {// 유망성을 체크하는 메소드
        for (int i = 0; i < column; i++) {

            if (board[column] == board[i]) // 같은 행에 퀸
                return false;

            // 대각선 체크 - 열의 차와 행의 차가 같으면 대각선
            if (Math.abs(column - i) == Math.abs(board[column] - board[i]))
                return false;
        }

        return true;
    }
}