[백준 9663] N-Queen (Java) [백트래킹]

문제

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

 

 

알고리즘

백트래킹

 

 

풀이

특정 규칙을 파악하면 바로 풀 수 있는 문제이다.

15x15의 모든 경우의 수를 파악하게 된다면 15!이므로 시간초과가 나게 된다.

따라서 특정 조건에 맞는다면 재귀를 타게하고 조건에 맞지 않는다면 스킵하면 백트래킹 처리를한다.

체스를 놓을 때마다 각 행에 대해 퀸의 위치를 마킹하고, 만약 전에 놓았던 퀸이 있다면 퀸을 놓을 수 있는 위치를 파악하며 문제를 풀이한다.

 

 

코드

package com.company;

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

public class Test_BackTracking {
    static int N;
    static int[] chess;
    static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N= Integer.parseInt(bf.readLine());

        chess = new int[N];
        go(0);
        System.out.println(ans);
    }

    //idx: 현재 체스를 놓을 행
    public static void go(int idx){
        if(idx>=N){
            ans++;
            return;
        }

        //현재 체스를 놓을 열
        for(int i=0; i<N; i++){
            boolean isCheck=true;
            //전에 체스를 놓았던 행
            for(int j=0; j<idx; j++){
                //세로 축 비교
                //chess[j] = 전에 체스를 놓았떤 열
                if(i==chess[j]){
                    isCheck=false;
                    break;
                }
                //대각선 축 비교
                if(Math.abs(i-chess[j])==Math.abs(idx-j)){
                    isCheck=false;
                    break;
                }
            }

            if(isCheck) {
                chess[idx] = i;
                go(idx + 1);
            }
        }
    }
}