[백준 9663] N-Queen (java)

문제보러가기

9663번: N-Queen

이 문제는 그 유명한 N-Queen 문제로 체스판에 퀸을 서로 공격할 수 없게 놓는 방법이 몇 가지가 있는지를 구하는 문제이다. 

 

분명히 학교 다닐 때 배웠던 거 같은데,, 까먹지 말도록 기록!

 

 

 

 

문제풀이

<규칙>

-같은 열(row)에 다른 퀸이 있으면 해당하는 곳은 놓을 수 없다.

-같은 행(col)에 다른 퀸이 있으면 해당하는 곳은 놓을 수 없다.

-해당 위치의 대각선에 다른 퀸이 있으면 해당하는 곳은 놓을 수 없다.

 

 

-board [row]=col 배열을 통해 해당 row에 어느 위치에 퀸을 놓았는지를 저장하면서 진행한다.

-반복문을 통해 0~n-1까지 col에 다 퀸을 놓아보면서 재귀 함수를 통해 진행한다.

-놓기 전에 check() 함수를 통해 같은 col에 놓아진 퀸이 없고 && 대각선에도 없는지 확인한다.

-n-1의 row까지 퀸을 놓을 수 있다면 경우의 수 ans++ 해준다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Ex_9663 {
	static int[] board;
	static int n;
	static int ans=0;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		//N-Queen
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		board = new int[n];
		solve(0);
		System.out.println(ans);
		
	}
    //퀸을 놓을 수 있는지 검사
	static boolean check(int row) {
    	//현재 row보다 이전 row들의 퀸들을 검사
		for(int i=0;i<row;i++) {
        	//같은 col , 대각선에 위치할 경우 return false
			if(board[i] == board[row] || (row - i) == Math.abs(board[i] - board[row])) {
				return false;
			}
		}
		return true;
	}
	static void solve(int row) {
    	//체스판의 끝까지 갔다면 모든 퀸을 다 놓았다는 의미
		if(row >= n) {
			ans++;
			return;
		}
        //각 col마다 퀸을 놓아보고 체크
		for(int col=0;col<n;col++) {
			board[row] = col;
			
			if(check(row)) {
				solve(row+1);
			}
		}
	}

}

 

 

아래 코드는 백트래킹, 이중 배열을 이용해서 풀이한 다른 분의 코드를 가져와봤다.

다른 분들의 코드도 많이 보면서 다양한 풀이 방법을 익혀야겠다.

 

public class Main{

	static int N, data = 0;
	static int[][] result, check;
	
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		result = new int[N][N];
		check = new int[N][N];
		
		dfs(0);
		
		System.out.println(data);
	}
	
	static void dfs(int num) {
		
		if (num == N) {
			data++;
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (num != 0) {
				if (check[num][i] > 0) {
					continue;
				}
			}
			
			//false로 만들기
			int p = i, m = i;
			for (int j = num + 1; j < N; j++) {
				p++;
				m--;
				if (p < N) {
					check[j][p] += 1;
				}
				if (m >= 0) {
					check[j][m] += 1;
				}
			}
			
			for (int j = num + 1; j < N; j++) {
				check[j][i] += 1;
			}

			dfs(num + 1);
			
			//true로 만들기
			int p1 = i, m1 = i;
			for (int j = num + 1; j < N; j++) {
				p1++;
				m1--;
				if (p1 < N) {
					check[j][p1] -= 1;
				}
				if (m1 >= 0) {
					check[j][m1] -= 1;
				}
			}
			
			for (int j = num + 1; j < N; j++) {
				check[j][i] -= 1;
			}

		}
	}
	
	
}