[Java] BOJ 9663 N-Queen (DFS)

DAUN JO·2021년 10월 6일

DFS algorithm boj

BOJ

목록 보기

33/35

BOJ 9663 G5 N-Queen

gold5
DFS

🔍 문제 설명

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

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

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

✔ 입력

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

✔ 출력

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

💡 풀이

퀸은 상하 좌우 대각선 중 한 방향으로 원하는 만큼 이동할 수 있다.
즉 퀸이 서로 공격할 수 없으려면,
같은 행, 같은 열, 같은 대각선을 피해 퀸을 놓아야 한다.

먼저 map[row]=col 형식으로 각 행 어느 열에 퀸을 놓았는지 체크한다.

퀸을 놓기 위해 dfs를 사용하고 매개변수는 현재 행의 위치인 row를 넘겨준다.

	private static void dfs(int row) {
	if(row==N) {
		ans++;
		return;
	}
	
	for(int col = 0 ; col < N ; col++) {
		
		if(canGo(row, col)) {
			map[row] = col;
			dfs(row+1);
		}
	}
}

0부터 N-1까지 탐색하여 퀸을 놓을 수 있다면 (같은 열에 퀸이 없고, 대각선에 퀸이 없다면) 퀸을 놓고 row+1하여 depth를 증가시켜 재귀 함수를 호출한다.

	private static boolean canGo(int row, int col) {
	for(int r = 0 ; r<row ; r++) {
		if(map[r] == col) return false; //같은 열에 있다
		if(Math.abs(r - row)==Math.abs(map[r] - col)) return false; //대각선
	}
	return true;
}

row==N이 된다면 퀸을 N개 모두 배치한 것 이므로 정답 카운트를 증가시킨다.

💬 소스코드

package boj.브루트포스;

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

/***
 * 
 * 
 * ✨ Algorithm ✨
 * @Problem : BOJ 9663 NQueen
 * @Author : Daun JO
 * @Date : 2021. 10. 6. 
 * @Algorithm : DFS
 *
 */

public class Main_BOJ_9663_G5_NQueen {
	static int N, map[], ans;
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		//같은 열에 다른 퀸이 있으면 X
		//같은 행에 다른 퀸이 있으면 X
		//대각선에 다른 퀸이 있으면 X
		//map[row]=col . (r,c) 체크

		map =new int[N];

		dfs(0);
		
		System.out.println(ans);
		
	}
	
	private static void dfs(int row) {
		if(row==N) {
			ans++;
			return;
		}
		
		for(int col = 0 ; col < N ; col++) {
			
			if(canGo(row, col)) {
				map[row] = col;
				dfs(row+1);
			}
		}
	}

	private static boolean canGo(int row, int col) {
		for(int r = 0 ; r<row ; r++) {
			if(map[r] == col) return false; //같은 열에 있다
			if((row-r)==Math.abs(map[r] - col)) return false; //대각선
		}
		return true;
	}
}