[SW Expert Academy] N-Queen (D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

 

import java.util.Scanner;

class Solution {

	public static int[] v1, v2, v3;
	public static int ans;
	public static int N;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();

		for (int tc = 1; tc <= t; tc++) {
			 N = sc.nextInt();
			v1 = new int[N]; //열에서 중복 찾음
			v2 = new int[2 * N]; //오른쪽 대각 중복 찾음
			v3 = new int[2 * N]; //왼쪽 대각 중복 찾음

			dfs(0);

			System.out.println("#" + tc + " " + ans);

			ans = 0;

		}
	}

	public static void dfs(int n) {

		if (n == N) {
			ans++;
			return;
		}

		for (int j = 0; j < N; j++) {
			if (v1[j] == 0 && v2[n + j] == 0 && v3[n - j + N] == 0) {
				v1[j] = v2[n + j] = v3[n - j + N] = 1;
				dfs(n + 1);
				v1[j] = v2[n + j] = v3[n - j + N] = 0;
			}
		}

	}
}

 

n-j+N을 한 이유는 자바에서는 -인덱스가 없기 때문에 +N만큼을 더해줬다.

범위를 벗어나지 않는 선에서 같은 수를 더해주면 되기 때문

ex) -2 -3에 +4를 하면 +2,+1이 된다.

이것들끼리 겹치지 않는 것을 구한 것

 

 

아래  링크를 참고했다.

https://www.youtube.com/watch?v=1Bh6DBcKgOc&t=494s

---

참고

https://infodon.tistory.com/61

[백준][JAVA알고리즘]9663번 풀이(N-Queen) - 초보도 이해하는 풀이

* arr = { 0,3,1,2,4}