문제 이해

N-Queen 문제는 대학교 수업에서도 들었던 예제일 정도로 유명한 문제이다.
문제는 간단하다.

체스판에서 퀸은 대각선과 상하좌우 칸 수 제한 없이 움직일 수 있다.
이 때 N * N 체스판에서 N개의 Queen이 서로 공격할 수 없게 Queen을 배치하는 경우의 수를 구하는 것이다.

---

문제 풀이

'백트래킹'이라는 방법을 활용한다.

알고리즘에서 따로 설명하지는 않았지만, Brute-Force에서 조금이라도 경우의 수를 줄이는 방법이다.

알다시피 DFS같은 경우 Node에 다다를 때 까지 모든 경우를 Search하기 때문에, 만약 중간 Node에서 이 Node 아래로 확인 하지 않아도 답이 되지 않을 것이라는 것을 알고 있어도 끝까지 연산을 수행해야 한다.

예를 들어, 3판 2선승 가위바위보를 할 때, A라는 사람이 B라는 사람에게 2번 이겼다면 우리는 현실에서 마지막 승부를 하지 않아도 A가 이겼다는 사실을 알 수 있다.

하지만, Brute-Force는 모든 경우의 수를 확인해야 하기 때문에 마지막 3번째 가위바위보까지 시행되어야지만 A가 이겼다는 것을 판정할 수 있다.

이런 쓸모없는 계산을 줄이기 위해 활용되는 것이 백트래킹이다.

백트래킹은 어떤 경우를 확인한 이후, 뒤에 어떠한 일이 있더라도 답이 될 수 없다는 것이 판별된다면 더 이상 그 Route에 대한 계산을 멈추는 것이다.

위에서 예시로 든 가위바위보에서는, A가 2승을 했거나 2패를 했을 경우 A가 몇 경기를 했든지 관계 없이 승리 여부는 명확하기 때문에 판정을 미리 종료시킨 이후 다른 Route를 확인하는 것을 말한다.

여기서는 Queen을 (T,K)에 둔다고 가정하였을 때, 1~(T-1)번째 행에 두었던 Queen 위치를 확인하고 만약 공격할 수 있다면 (T,K)에 둔 이후 (T+1) ~ N번째 행에 둔 경우의 수는 아예 고려하지 않아도 된다.(어차피 (T,K)에 둔 Queen이 조건을 불만족시키기 때문)

따라서 (T,K)에 대한 하위 연산을 멈추고, (T,K+1)에 두는 상황 확인으로 바로 넘어가는 방법으로 백트래킹을 활용한다.

---

코드

import java.util.*;

public class Main {
	static int N;
	static int[][] queen; 
	static int answer = 0;
    // 1 ~ (K-1)번째 행에 Queen을 둔 위치를 저장하는 행렬
    // 1일 경우 해당 위치에 Queen이 두어져 있다는 것을 의미한다.
	
	static boolean check(int x,int y) { 
        // Queen이 공격 받지 않는 (x,y)에 두어져 있는지 확인하는 방법
        // 배치할 수 있으면 True, 배치 할 수 없으면 False를 반환한다.

		for(int i =0;i<x;i++) {
            // 0 ~ (x-1) 행의 queen 배열에만 Queen이 배치되어 있을 것이다.
            // 따라서, 0 ~ (N-1)까지 전부를 확인하지 않고, (x-1)까지만 확인한다

			if(queen[i][y]!=0) { // 같은 열에 존재하여 공격 가능할 경우
				return false;
			}
			
			int upper = y - Math.abs(x-i);
			int lower = y + Math.abs(x-i);
			
            // 대각선에 존재할 경우 (2가지 존재)
			if(upper>=0 && queen[i][upper]!=0) { 
                // 1. (2,2)일 때 (1,1)에 존재할 경우 
                // 즉, 왼쪽 대각선 방향에 Queen이 존재할 경우
				return false;
			}
			
			if(lower<N && queen[i][lower]!=0) {
                // 2. (2,2)일 때 (1,3)에 존재할 경우 
                // 즉, 오른쪽 대각선 방향에 Queen이 존재할 경우
				return false;
			}
		}
		
		return true;
	}

	static void rec_fun(int x) { //재귀 함수
        // x : 이번에 배치 시킬 Queen의 행
		
		if(x==N) { 
            // x = N이라는 것은 모든 위치(0 ~ N-1 행)에 서로 공격하지 않도록
            // Queen이 배치되었다는 것을 의미한다. 
            // 따라서 경우의 수를 하나 추가 시킨 후 return 시킨다.
			answer++;
			return;
		}
		
		for(int y =0;y<N;y++) {
			if(check(x,y)) { 
                //check(x,y) = true여서 (x,y)에 queen을 둘 수 있을 때 실행됨
				queen[x][y] = 1;
				rec_fun(x+1);
				queen[x][y] = 0;
			}
		}
	}
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		queen = new int[N][N];
		
		rec_fun(0);
		
		System.out.println(answer);
	}
}

---

결과