[백준] 9663번 : N-Queen(JAVA)

언제쯤 알고리즘 마스터가 될까

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

9663번: N-Queen

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 13단계

 

백트래킹의 카테고리에 포함되어 있는 문제이다.

 

이 문제는 크기가 N * N인 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제이다.

 

체스판에서 퀸은 가로세로대각선을 모두 공격할 수 있는 최고의 말이다.

 

visit_a과 visit_b는 바로 다음행의 각각 바로위의 대각선에 퀸을 놓지 않기 위해 선언한 배열이다.

 

'자료구조와 함께 배우는 알고리즘 입문'을 참고하여 푼 문제이다.

 

백트래킹에 대한 개념은 이해가 거의 끝나가는 것 같지만

 

백트래킹을 문제에 적용하는 법은 아직 미숙한 것 같다.

 

더더욱 열심히 공부하여 노력하여야겠다.

 

import java.util.Scanner;

public class Question_9663 {
	static int N;
	static boolean[] visit;
	static boolean[] visit_a;
	static boolean[] visit_b;
	static int count = 0;
	
	static void Backtracking(int index) {
		for(int i = 0; i < N; i++) {
			if(visit[i] == false &&
               visit_a[index + i] == false &&
               visit_b[index - i + (N-1)] == false) {
               
				if(index == N-1) {
					count++;
				} else {
					visit[i] = visit_a[index + i] = visit_b[index - i + (N-1)] = true;
					Backtracking(index + 1);
					visit[i] = visit_a[index + i] = visit_b[index - i + (N-1)] = false;
				}
                
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		visit = new boolean[N];
		visit_a = new boolean[N*2-1];
		visit_b = new boolean[N*2-1];
		
		Backtracking(0);

		System.out.println(count);
	}

}