백준 | 9663번. N-Queen - 백트래킹(DFS) 문풀

⬛ 백준 9663번. N-Queen - 백트래킹(DFS) 문풀

https://www.acmicpc.net/problem/9663

9663번: N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

---

💚 문제 접근 방식

이 문제는 내가 직접 풀다가 실패해서 풀이를 찾아봤고 이해한 내용을 토대로 적었다.
[실패 지점] : 이차원 배열로 체스를 구현해서 모든 행과 열에 대한 위치가 퀸이 놓을 수 있는 위치인지 확인하려고 시도했는데 시간 초과가 떴다.

 

체스 게임에서 퀸이 공격할 수 있는 영역은 같은 행, 같은 열, 같은 대각선에 위치한 영역이라는 것을 알아두자.

1) N X N 에서 퀸 N개를 둘 수 있는 전체 방법의 수를 구해야 한다.
2) N=4라고 하면 칸이 16칸이 나오는데, 어떤 칸에 퀸을 두는 지에 따라 다음 퀸을 어디에 둘 수 있는지도 달라지므로 백트래킹으로 모든 경우의 수를 다 순회하면서 탐색해보고 경우의 수를 따져봐야 전체 몇 가지 방식으로 N개 퀸을 둘 수 있는지 알 수 있다.

풀이 설명

---

결과적으로, 백트래킹으로 이 문제를 접근하려면 다음의 사고 과정을 거쳐야 한다.
 체스판은 N X N 2차원 배열이다.
  N = 4라고 하더라도, 한 가지 사건에서 퀸을 둘 수 있는 경우가 16칸이나 되는데
  매 깊이마다 16케이스를 모두 따져가며 다음 깊이로 이동하는 방식은 굉장히 비효율적이고 시간복잡도가 커지는 방식이다.
  일단 체스판이 공격성을 닿는 부분은 같은 행이거나 같은 열이거나 같은 대각선상에 위치한 영역이다.
  그 말은 한 행에 1개의 퀸, 한 열에도 1개의 퀸, 한 대각선 상에도 1개의 퀸만 존재한다는 것이다.

풀이 설명 2

[ 깊이 탐색 예시 그림 ] 

DFS 탐색 그림 설명

---

💚 제출 코드

import java.util.Scanner;

/**
 * 9963번. N-Queen - 백트래킹 문풀  
 * @author MYLG
 *
 */
public class Main {
	static int count = 0;
	static int N;
	static int[] arr;
	
	//DFS
	static void DFS(int row) { //행에 대한 깊이탐색 시도 
		if(row == N) {
			count++;//여기까지 깊이 행이 도달했다면 모든 행에 퀸을 두었다는 것이므로 ++처리 
			return;
		}
		
		for(int i=0; i<N; i++) {
			arr[row] = i;//현재 깊이의 행에 퀸 위치를 i열에 둔다
			if(isPossible(row)) {
				DFS(row+1);//다음 깊이로 이동
			}
		}
	}
	
	//isPossible
	static boolean isPossible(int row) {
		for(int i=0; i<row; i++) {
			if(arr[i] == arr[row]) {
				//들어온 행에대한 열과 같은 열값을 갖는 게 이전 arr에 있었는지 확인 
				return false;//그 위치는 공격가능한 영역이므로 
			}
			
			//들어온 직전 행, 현재 찍은 i행 차이와 직전 열 - 현재 i열의 차가 같은 경우 동일 대각선상에 존재하는 퀸이 존재하므로 안됨 
			if(Math.abs(i-row) == Math.abs(arr[i]-arr[row])) {
				return false;
			}
		}
		return true;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		N = kb.nextInt();
		arr = new int[N];
		
		DFS(0);
		
		System.out.println(count);
		
	}
}