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

이전과 마찬가지로 백트래킹에 관련된 문제 중 가장 어려웠던 N-Queen 문제를 풀었다.

 

백트래킹에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/3

알고리즘 - 백트래킹(Backtracking)

---

<문제>

<문제 해석>

주어진 N에 대해 크기가 N x N 인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력하라.

 

 

<문제 해결>

나는 체스에 대해 아는 것이 없었기 때문에 체스에서 Queen이 이동할 수 있는 범위를 전혀 몰랐다.

먼저, 체스에서 queen이 이동할 수 있는 범위부터 찾아보기 시작했다.

 

 

👇아래의 블로그를 참고하여 queen의 이동을 알아내었다.

https://opentutorials.org/module/3806/22853

체스 기물의 행마법 - 체스의 기초

 

 

체스에서 queen이 이동할 수 있는 범위는 상하좌우, 대각선이다.

4 x 4의 체스판에서 노란색이 퀸이라면 빨간색 화살표들이 퀸이 이동할 수 있는 범위인 것이다.

<알고리즘>

1. 체스판에 퀸 하나를 배치한다.

2. 퀸이 위치한 자리에서 다른 퀸이 있지 못하는 자리 (상하좌우, 대각선) 를 판별한다. 

3. 다른 퀸이 위치할 수 있는 자리라면 그 자리에 퀸을 배치한다.

4. n개의 퀸을 다 배치할 때까지 1,2,3 단계를 반복한다.

 

 

나는 queen의 위치를 1차원 배열로 나타내었다.

각 원소의 index값 => "열",  원소 값 => "행" 으로 구분했다.

 

 

위의 그림에서 노란색 퀸의 위치를 배열로 나타내면 1열 1행이므로

[0,1,0,0] 으로 표현할 수 있다.

 

<코드>

import java.io.IOException;
import java.util.Scanner;

class Main{
	static int n;
	static int count=0;
	static int a[];
	
    public static void main(String[] args) throws NumberFormatException, IOException {
    	Scanner sc = new Scanner(System.in);
    	
    	n = sc.nextInt();
    	a = new int[n];
    	
    	backtracking(0);
    	
    	System.out.println(count);
    	
    }
    
    public static void backtracking(int index) {
    	
    	if(index == n) {
    		count++;
    		return;
    	}
    	
    	for(int i=0;i<n;i++) {
    		a[index] = i;
    		
    		if(check(index)) {
    			backtracking(index+1);
    		}
    	}
    
    }
    
    public static boolean check(int col) {
    	
    	for(int i=0;i<col;i++) {
    		//같은 행
    		if(a[col] == a[i]) {
    			return false;
    		}
    		//대각선
    		else if(Math.abs(col - i) == Math.abs(a[col] - a[i])) {
    			return false;
    		}
    	}
    	
    	return true;
    }
}

 

백트래킹 문제에서 N-Queen 문제가 대표적인 문제인 만큼 해결하는데 시간이 많이 걸렸다.

그 뜻은 아직 백트래킹을 완전히 마스터하지 못했다는 말인 것이다.

다른 백트래킹 관련 문제들도 풀면서 백트래킹을 마스터 해야겠다!!!🔥🔥🔥

 

 

---

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

9663번: N-Queen