[SWEA] - 2806. N-Queen (D3)

[문제]

8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다.
퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다.

이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다.
N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇가지가 있을까?
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 하나의 자연수 N(1 ≤ N ≤ 10)이 주어진다.

[출력]
각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다

문제 풀기

2806. N-Queen

 

---

[풀이]

• 백트래킹(Backtracking) 알고리즘을 이용하여 풀이
• q 배열에 퀸이 들어가는 위치를 담는데, 1차원 배열로 받는다. >> index 값은 열, 원소 값은 행으로 생각한다.
• 다른 퀸과 같은 행에 있는지, 대각선에 있는지 검사한다.
• 퀸을 놓을 수 있는 위치면 다음 재귀를 호출, 놓을 수 없으면 다음 반복문으로 넘어간다.

백트래킹(Backtracking)이란?
비효율적인 경로를 차단하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방법
DFS에 가지치기 (Pruning) 를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법

import java.util.Scanner;

class Solution {
	static int n;
	static int q[];
	static int result;
	
	public static void main(String[] args) throws Exception {		
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			result = 0;
			n = sc.nextInt();
			q = new int[n];
			backtrack(0);
			System.out.format("#%d %d\n", tc, result);
		}
	}
	
	static void backtrack(int row) {
		if(row == n) {
			result++;
			return;
		}
		for(int i=0; i<n; i++) {
			q[row] = i;
			if(ok(row)) {
				backtrack(row + 1);
			}
		}
	}
	
	static boolean ok(int col) {
		for(int i=0; i<col; i++) {
			if(q[col] == q[i]) return false;
			if(Math.abs(col-i) == Math.abs(q[i]-q[col])) return false;
		}
		return true;
	}
}