[백준] 9663 N-Queen - Java

 

 

 

백트래킹을 사용해서 풀 수 있다.

 

import java.util.*;
import java.io.*;


// 엔퀸
 public class Main1 {

    static int ans;
    static int N;
    static int col[]; // 퀸의위치저장용 i , col[i]

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

        N = Integer.parseInt(br.readLine());
        col = new int[N+1];

        backtracking(1); // 1부터 시작해서 백트래킹함 dfs느낌으로

        System.out.println(ans);
    }

    static void backtracking(int row){
        if(row == N+1){ // N+1까지간거면 다돈거임
            ans++;
        }else{
            for(int c = 1; c <= N; c++){ // 칼럼먼저순회함 
                boolean chk = true;
                for(int i=1; i<=row-1; i++){ // 여러개의 퀸에대해서 싹다 조사함 공격되는지

                    if(attackable(row, c, i, col[i])){ // 공격가능하면 브레이크. 다음칼럼조사
                        chk = false;
                        break;
                    }
                }


                if(chk){ // 공격안당하면 갱신해줌 일단 퀸하나놓고 다음 ㄱㄱ 
                    col[row] = c;                  
                    backtracking(row+1);
                    col[row] = 0; // 다음까진 잘갔는데 브레이크걸리면 이 루트 싹다 초기화 다음row부터 조사하게함
                }

            }
        }
    }


    static boolean attackable(int r1, int c1, int r2, int c2){
        if(c1 == c2){
            return true; // 와이좌표같으면 공격가능 일단 위에서 엑스좌표는 고려하니까
        }
        
        if(Math.abs(c1 - c2) == Math.abs(r1 - r2)){ // 대각선은 이거로 고려한다
            return true;
        }

        return false; // 나머지는 공격못하는거 
    }


}