[BAEKJOON_9663 - JAVA] N-Queen

문제

www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

풀이

※ 퀸은 위와같이 직선과 대각선 방향으로의 이동 제한이 없다.

 

 

1. 첫번째 열에 퀸을 해당 위치 놓는 경우 해당 행,열,대각선에는 다른 퀸을 놓을 수 없다.

 

 

2.  다음 열에서 퀸을 놓을 수 있는칸에 다른퀸을 추가한 뒤, 놓을 수 없는칸을 표시

 

 

3.  다음 열 또한 마찬가지로 추가

 

 

4. 다음과 같은 결과를 얻을 수 있다.

 

 

위와 같은 과정으로 열을 기준으로 퀸을 놓을 위치를 탐색해 나간다.

2차원 배열로의 탐색보다 index를 '열' 이라 생각하며, 원소값을 '행' 이라 생각하는 것이 더 편리.

ex) arr[3] =5 인 경우, 3열 5행으로 표현.

 

 

과정

1. index를 depth로 다루는 dfs 탐색.
2. '열'을 기준으로 dfs.
   → dfs 함수
3. 해당 위치에 배치 가능 여부 검사. 
   행or열이 동일한 경우와 대각선(col의 차이 == row의 차이)에 위치하는 경우 배치 불가.
   → possible 함수
4. 열의 크기 만큼 dfs를 호출한 경우 결과값 증가.

 

 

알고리즘 지식

• 브루투포스
• 백트래킹

 

 

JAVA코드

package BaekJoon_2020_12_22__23;

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

/**
 * @packageName : BaekJoon_2020_12_22
 * @fileName : BJ_9663_N_Queen.java
 * @author : Mingeon
 * @date : 2020. 12. 22.
 * @language : JAVA
 * @classification :
 * @time_limit : 10sec
 * @required_time : 21:36 ~ 00:00
 * @submissions : 2
 * @description 
 * 1. 2차원이 아닌 '행'or'열'을 고정하여 풀이.
 */

public class BJ_9663_N_Queen {
	static int N; // 퀸의 개수, 판의 크기
	static int[] chessMap; // 체스판
	static int cnt; // 방법의 개수

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); // End of input
		chessMap = new int[N]; // 체스판 index는 열을 가르킨다. chessMap[1] -> 1열
		cnt = 0;
		dfs(0);

		System.out.println(cnt);
		br.close();
	}

	// depth -> 열이 된다
	private static void dfs(int depth) {
		// 행을 다 채운 경우
		if (depth == N) {
			cnt++;
			return;
		}

		for (int i = 0; i < N; i++) {
			chessMap[depth] = i;
			// possible : 해당 열에서 i번째 행에 높을 수 있는지 체크
			if (possible(depth)) {
				dfs(depth + 1);
			}
		}

	}

	// 퀸을 배치 가능 여부 검사
	private static boolean possible(int col) {

		// 해당 열(col) 전까지만 탐색
		for (int i = 0; i < col; i++) {
			// 같은 행에 존재하는 경우
			if (chessMap[col] == chessMap[i]) {
				return false;
			}

			// 대각선에 놓인 경우
			else if (Math.abs(col - i) == Math.abs(chessMap[col] - chessMap[i])) {
				return false;
			}
		}
		return true;
	}

}