[백준 9663번] N-Queen

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

9663번: N-Queen

이 문제는 백트래킹 알고리즘의 대표적인 문제 중 하나로, 골드 4 문제입니다.

---

해결책

 이 문제를 해결하기 위해 백트래킹의 개념을 알아야합니다. 백트래킹은 기존 끝까지 탐사하는 DFS와 달리 만약 탐색하고 있는 값이, 옳지 않다 생각하면, 바로 전 노드 단계로 돌아가버려 그 다음 단계를 수행합니다. 그럼으로써 효율적이게 탐색을 할 수 있는것입니다. 

<Wikipedia>

위 그림을 보시면, 백트래킹에 대해 잘 나타내고 있습니다. 일단 해당 자리에 퀸을 놓는다 했을때, 겹치면 바로 전 단계로 돌아간다는 것이죠, 그럼 이 퀸을 놓을 떄 겹치지 않는 조건은 무엇일 까요?

1.놓는 자리에 겹치는 열이 없어야 한다.

퀸은 겹치지않게, 매 n의 퀸을 놓을떄, n번째 행에 놓는다고 가정하면, 겹치는 열이 없어야 합니다. 퀸은 직선과, 대각선으로 이동할 수 있으니까요, 그러므로 n번째, 퀸의 자리가 (x,n)일때, 저 x랑 같은 값을 가지는 값이 없어야한다는 것입니다

2. 놓는 자리의 대각선에도 겹치지 말아야한다.

만약 놓는자리의 퀸의 자리가 (2,2)라고 가정합시다 이때 (1,1)에 퀸이 놓여있으면, 겹치므로 놓을 수 가 없습니다. 만약 해당 퀸의 자리가 (2,3)이라고 합시다, 이때 (1,2)에 퀸이 놓여 있으면, 겹칩니다. 그럼 이 차이는 어떻게 알 수 있을까요?

바로 n번째 자리의 퀸의 행- (n-1)번째 퀸의 행 = |n번째 자리의 퀸의 열 - (n-1)번째 자리의 퀸의 열| 이면, 대각선에도 겹치는 것입니다. 대각선이 항상 (x,y)의 차이가 일정하게 가기 때문이죠. 때문에 그걸 고려하며 코드를 작성해 줘야 합니다.

 

코드

import java.io.*;
import java.util.*;
public class Main {
	static int [] chess;
	static int count=0;
	public static void sol(int n,int s) {
		if(n==s) {
			count++;
			return;
		}else {
			for(int i=0; i<s;i++) {
				chess[n]=i;
				if(promise(n)) {//증명한 뒤 놓을 수 있으면 다음 단계로 넘어간다
					sol(n+1,s);
				}
			}
		}
	}
	public static boolean promise(int n) {
		for(int i=0;i<n;i++) {
			if(chess[n]==chess[i]||n-i==Math.abs(chess[n]-chess[i]))
				return false;
			
		}
		return true;
	}
	public static void main(String args[]) {
		Scanner sc=new Scanner(System.in);
		int n = sc.nextInt();
		chess=new int[n+1];
		sol(0,n);
		System.out.println(count);
		
		
	}

}