[SWExpert] 2806. N-Queen

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE

SW Expert Academy

N-Queen은 백 트래킹 문제의 대표이다. 

백 트래킹 설명 :  https://hee96-story.tistory.com/57?category=827781

[알고리즘] Backtracking (백 트래킹)

배운 점

• 대각선상에 놓여있는 것을 확인할 때, x좌표의 차와 y좌표의 차가 동일하면 (절대값 기준) 대각선상에 놓여있는 것이다.

• 예를 들어, 4*4일 때 (2,1)과 (0,3)는 같은 대각선에 놓여있다. --> |2-0| == |1-3|

---

코드

package swexpert.D3;

import java.util.Scanner;

public class N_Queen_SW2806 {
    static int result = 0;
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 1; t <= tc; t++) {
            n = sc.nextInt();
            result = 0;
            int col[] = new int[n];
            for (int i = 0; i < n; i++) {
                col[0] = i;
                queen(col, 0);		//dfs를 사용한다.
            }
            System.out.println("#"+t+" "+result);
        }
    }

    private static void queen(int col[], int row) {
        if (row == n - 1) {
            result++;
            return;
        } else {
            for (int i = 0; i < n; i++) {
                col[row + 1] = i;
                if (check(col, row + 1))		//퀸을 놓을 수 있는지 확인한다.
                    queen(col, row + 1);
            }
        }

    }

    private static boolean check(int col[], int row) {
        //col과 대각선에 퀸이 있는지 확인하는 함수
        for (int i = 0; i < row; i++) {
            //col : row의 행까지 같은 col에 위치하는 퀸이 있는지 확인
            if (col[i] == col[row])
                return false;
            //대각선 : 대각선에 위치하면, 두 좌표의 x 좌표의 차와 y 좌표의 차는 같다.
            if (Math.abs(row - i) == Math.abs(col[row] - col[i]))
                return false;
        }

        return true;
    }


}