[BOJ] 9663 N-Queen(Backtracking 대표 문제)

문제

www.acmicpc.net/problem/9663

9663번: N-Queen

풀이

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


public class BOJ_9663 {
    static int N,answer;
    static int[] chessPane;
    static int cnt;
    static boolean isPossible(int col){
        for(int i=0;i<col;i++){
            if(chessPane[col] == chessPane[i])
                return false;
            else if(Math.abs(col-i) == Math.abs(chessPane[col]-chessPane[i]))
                return false;
        }
        return true;
    }
    static void backtracking(int depth){
        if(depth == N){
            cnt++;
            return;
        }
        for(int i=0;i<N;i++){
            chessPane[depth] = i;
            if(isPossible(depth)){
                backtracking(depth+1);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        chessPane = new int[N];
        backtracking(0);
        System.out.println(cnt);
    }
}

 

풀이 중점 1) 체스판 배열을 2차원이 아닌 1차원으로도 표현할 수 있다.  

- index -> 열, chesspane[index] 원소 값 -> 행 으로 표현

- 열 값(index)을 변경해주면서 체스 말을 놓을 수 있는 지 없는지를 계속 판별한다.

- depth가 N이 될 때까지 말을 계속 놓을 수 있었다면, 이 경우는 맞는 경우이므로 cnt를 올려준다.

 

풀이 중점 2) 열의 값은 depth로 계속 변하는 값이니, 같은 행 혹은 대각선상의 위치에 있는지만 판별                    하면 된다.

 

풀이 중점 3) 대각선 값의 표현은 행의 좌표값의 차이와 열의 좌표값의 차이가 같음을 활용한다.

- 예를 들어 (0,0), (1,1) 두 좌표는 대각선상에 있는 경우이다. 이때 행 좌표값 차이 = 열 좌표값 차이 임을 알 수 있다.