[프로그래머스(Programmers)][자바(java)] (Lv3) N-Queen

 

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

코딩테스트 연습 - N-Queen

 

 

문제 설명

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

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

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

 

제한사항

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

 

입출력 예

n	result
4	2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

 

문제 풀이

public class Solution {

	boolean[] flag_a, flag_b, flag_c;	// 각행, 대각선/, 대각선\에 퀸을 배치했는지
	int[] pos;							// 각 열의 퀸의 위치
	int num, cnt = 0;
	
	public void set( int i ) {
		for( int j = 0; j < num; j++ ) {
			if( flag_a[j] == false && flag_b[i+j] == false && flag_c[i-j+(num-1)] == false ) {
				pos[i] = j;
				if( i == (num-1) )
					cnt++;
				else {
					flag_a[j] = flag_b[i+j] = flag_c[i-j+(num-1)] = true;
					set( i + 1 );
					flag_a[j] = flag_b[i+j] = flag_c[i-j+(num-1)] = false;
				}
			}
		}
	}
	
	public int solution(int n) {
		flag_a = new boolean[n];
		flag_b = new boolean[2*n-1];
		flag_c = new boolean[2*n-1];
		pos = new int[n];
		num = n;
		set(0);
        return cnt;
    }

}

 

* 분기 한정법 ( 백트래킹 개선 )