[프로그래머스]N-Queen_Java

--문제--

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

코딩테스트 연습 - N-Queen

--문제 접근--

DFS의 대표적인 문제로

재귀적인 생각을 하는데 도움이 되는 문제입니다..

저는 DFS를 돌면서 Queen을 놓을 수 있는지 없는지 확인하면서 만약 놓을 수 있다면 다음 재귀로 들어가서 다 놓았을 시에 +1을 하면서 문제를 풀이하였습니다.

여기서 중요한 것은 대각선에 놓아져 있는지 확인하는 것이었는데

행의 차와 열의 차가 같다면 그것이 대각선이라는 것이었습니다.

		O
		↑이렇게 행의차 2
O	-> 이렇게 열의 차이 2	->↑

코드

package Level3;

import java.util.Arrays;

public class Nqueen {
	static int Goal,answer;
	static boolean[][] map;
	public static void main(String[] args) {
		System.out.println(solution(4));
	}
	public static int solution(int n) {
        answer = 0;
        Goal=n;
        map=new boolean[n][n];
        DFS(0);
        
        return answer;
    }
	private static void DFS(int idx) {
		if(idx==Goal) {
			answer++;
			for(boolean[] x :map)System.out.println(Arrays.toString(x));
			System.out.println();
			return;
		}
		for(int i=0;i<Goal;i++) {
			if(check(idx,i)) {
				map[idx][i]=true;;
				DFS(idx+1);
				map[idx][i]=false;
			}
		}
		
	}
	private static boolean check(int x, int y) {
		//세로체크
		for(int i=0;i<x;i++) {
			if(map[i][y])return false;
		}
		for(int i=0;i<x;i++) {
			for(int j=0;j<Goal;j++) {
				if(i==x&j==y)continue;
				if(Math.abs(x-i)==Math.abs(y-j)&&map[i][j])return false;
				
			}
		}
		
		return true;
	}
}