백준알고리즘:p9663 N-Queen

분류: 백트래킹

 

▶문제

먼저 체스게임에서 퀸의 능력은 원하는 만큼 상하좌우 대각선으로 이동할 수 있다. (다만, 한 방향으로만 가야됨)

N*N체스판에서 퀸 N개가 서로 공격하지 않도록 놓는 방법의 갯수를 출력해야 한다. 

아래 사진처럼 퀸이 움직인다. 

출처 : https://st-lab.tistory.com/118

즉 체스말이 현재 있는 곳에서 갈 수 있는 모든 곳을 x표시하고, 다른 말이 있는게 가능한 곳에서 또 x표시하는 반복을 한다. 

 

▶코드

//백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 
package backtracking;

import java.util.Scanner;

public class p9663_1 {
	public static int N;
	public static int[] arr;
	public static int count;	
	//가로줄 하나에 체스말 한개만 있을 수 있음
	//그래서 depth가 열이고 arr[depth]값이 세로줄 행인 셈이다. 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N];
		//arr[가로줄]에 체스말이 있는 행을 적어줄 것임. 
		nQueen(0);
		System.out.print(count);
		
		sc.close();
	}
	
	public static void nQueen(int depth) {
		if(depth==N) {//N개를 체스판에 놓았을 경우만 count (즉 depth는 현재 놓은 말갯수)
			count++;
			return;
		}
		
		for(int i=0; i<N; i++) {
			arr[depth] = i;// i는 행 _ arr[depth(=열)][i(=행)] 인 셈이다.
			if(posibility(depth)) {//해당 열에서 i번째 행에 놓을 수 있는지 검사./
				nQueen(depth+1);
			}
		}
	}
	
	public static boolean posibility(int col) {
		for(int i=0; i<col; i++) {
			if(arr[col]==arr[i]) {//같은 행(value)(세로줄)에 있는지 검사
				return false;
			}
			//대각선에 있는지 검사 :열의 차와 행의 차가 같으면 대각선에 있는 것이다.
			else if(Math.abs(col-i)==Math.abs(arr[col]-arr[i])){
				 return false;
			}
		}
		return true;
	}

}

▶2차원보다 1차원이 이해하면 쉽다. 2차원은 복잡..

 

 

 

 

---

채점결과

 

링크 www.acmicpc.net/problem/9663

9663번: N-Queen