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

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
n은 12이하의 자연수 입니다.

Code

class Solution {
    public int solution(int n) {
        return helper(new int[n], new boolean[n], 0);
    }
    
    public int helper(int[] arr, boolean[] visit, int cnt) {
		if(cnt==arr.length) {			
			return 1;
		}
		
		int ret = 0;
		
		for(int i=0; i<visit.length ; i++) {
			if(visit[i]) continue;
			boolean corr = true;
			arr[cnt] = i;
			for(int j=0 ; j<cnt ; j++) {
				if(Math.abs(cnt-j)==Math.abs(arr[cnt]-arr[j])) {
					corr = false;
					break;
				}
			}
			
			if(!corr) continue;
			visit[i] = true;
			ret += helper(arr, visit, cnt+1);
			visit[i] = false;
		}
		return ret;
	}
    
}