[프로그래머스] N-Queen

문제설명

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

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

 

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

제한사항

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

해결 방법

DFS와 백트레킹을 사용한 대표적인 예 n-queen.

 

DFS와 백트레킹을 사용했다.

 

https://dheldh77.tistory.com/154

[알고리즘] 되추적(Backtracking) 알고리즘

 

JAVA

package programmers;

import java.util.*;

public class p_12952 {
	static int[][] board;
	static int n;
	static int cnt;
	public static void dfs(int row, int col) {
		board[row][col] = 1;
		
		if(row == n - 1) cnt++;
		
		for(int i = 0; i < n; i++) {
			if(promissing(row + 1, i)) dfs(row + 1, i);
		}
		
		board[row][col] = 0;
	}
	
	public static boolean promissing(int row, int col) {
		for(int i = 0; i < row; i++) {
			if(board[i][col] == 1) return false;
		}
		for(int i = 1; i < n; i++) {
			if(row - i >= 0 && col - i >= 0 && board[row - i][col - i] == 1) return false;
			if(row - i >= 0 && col + i < n && board[row - i][col + i] == 1) return false;
		}
		
		return true;
	}
	public static int solution(int N) {
		n = N;
		board = new int[n][n];
		cnt = 0;
		for(int i = 0; i < n; i++) {
			dfs(0, i);
		}
		
		return cnt;
	}
	public static void main(String[] args) {
		System.out.println(solution(4));
	}
}