N-Queen (백준 9663번) - 백트래킹

10초

128 MB

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

---

 

<코드> 

import java.io.IOException;
import java.util.Scanner;


public class Main {
    static int[] map;
    static int res = 0 , N ;
    
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        for(int i = 0 ; i < N ; i++){
            map = new int[N];
            map[0] = i;
            backtracking(1);
        }
        System.out.println(res);
    }

    private static void backtracking(int row) {

        if(row == N){
            res++;
            map[row-1] = 0;
            return;
        }

        for (int i = 0; i < N; i++) {
            map[row] = i;
            if(possible(row)){
                backtracking(row+1);
            }else{
                map[row] = 0;
            }
        }


    }

    private static boolean possible(int row) {
        for (int i = 0; i < row; i++) {
            if(map[i] == map[row]) return false;
            if(Math.abs(row-i) == Math.abs(map[row] - map[i])) return false;
        }
        return true;
    }

}

---

<피드백>

- 백트래킹, DFS 문제를 풀때 논리적으로 재귀적으로 생각하는 연습하자