[프로그래머스/JAVA] N-Queen

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

가로와 세로의 길이가 n인 체스판에 서로를 공격할 수 없는 n개의 퀸을 놓을 수 있는 경우의 수를 구하는 문제

퀸은 가로, 세로, 대각선으로 이동할 수 있음 = 공격할 수 있음 -> 가로, 세로, 대각선으로 겹치지 않도록 퀸을 두어야 함

visitedC : 해당 열에 말이 있으면 true, 말이 없으면 false

visitedA : 정비례 그래프 모양의 대각선 방향

visitedB : 반비례 그래프 모양의 대각선 방향

class Solution {
    static int cnt;
    public int solution(int n) {
        int answer = 0;
        cnt = 0;
        
        dfs(0, 0, new boolean[n], new boolean[2*n], new boolean[2*n-1], n);

        return answer = cnt;
    }
    public void dfs(int qnum, int r, boolean[] visitedC, boolean[] visitedA, boolean[] visitedB, int n) {
		if(qnum == n && r == n) {
			cnt++;
			return;
		}
		
		for(int i=0; i<n; i++) {
			if(!visitedC[i] && !visitedA[i-r+n] && !visitedB[i+r]) {
				visitedC[i] = true;
				visitedA[i-r+n] = true;
				visitedB[i+r] = true;
				dfs(qnum+1, r+1, visitedC, visitedA, visitedB, n);
				visitedC[i] = false;
				visitedA[i-r+n] = false;
				visitedB[i+r] = false;
			}
		}
	}
}