[프로그래머스] N-Queen -Java

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

코딩테스트 연습 - N-Queen

class Solution {
		int answer;
		int dx[]= {0,0,1,-1,-1,-1,1,1};
		int dy[]= {-1,1,0,0,-1,1,-1,1};
	    public int solution(int n) {
	    	answer=0;
	    	int [][]map = new int[n][n];
	    	solve(map,n,0);
	        return answer;
	    }
		private void solve(int[][] map, int n, int cnt) {
			if(cnt==n) {
				answer++;
				return;
			}
			
			for(int i=0; i<n; i++) {
				if(!isBound(map,cnt,i,n)) continue;
				map[cnt][i]=1;
				solve(map,n,cnt+1);
				map[cnt][i]=0;
			}
			
		}
		private boolean isBound(int[][] map, int x, int y, int n ) {
			for(int i=0; i<8; i++) {
				int nx=x;
				int ny=y;
				
				while(true) {
					nx+=dx[i];
					ny+=dy[i];
					if(nx<0 || ny<0 || nx>=n || ny>=n) break;
					if(map[nx][ny]==1) return false;
				}
			}
			return true;
		}
	}

소요시간 : 15분

 

전형적인 백트래킹 문제였습니다.

 

예전에서 백준에서 비슷한 문제를 풀어봐서 금방 푼 것 같습니다.

 

isBound함수에서 현재 위치에 퀸을 놓았을 때 다른 퀸을 공격할 수 있는지 확인합니다 (8방향 확인)

 

백트래킹을 위해 DFS함수에 들어가기 전에 map[cnt][i]를 1로 만들고    (cnt : 행 , i : 열)

DFS가 끝나고 나올 때는 map[cnt][i]를 0으로 만들어 주었습니다.