9663번 - N-Queen

1️⃣ 백트랙킹

 

✏️ 풀이 과정

NxN 체스판에 N개의 퀸을 서로 공격할 수 없게 놓는 유명한 백트랙킹 문제입니다. 기본적인 원리는 각 행이나 열을 기준으로 모든 자리에 놓아보며 테스트하다가 불가능한 경우라는 것을 알게되었을 때 이전 단계로 돌아가는 것입니다.

 

기본적인 설명은 위와 같지만 실제로는 직접 돌아가는 로직을 작성하지는 않고 재귀 함수를 활용해서 불가능한 경우는 다음 단계로 나아가지 않도록 하여 가능한 경우에만 끝까지 진행되도록 설계합니다.

 

아래 코드는 크게 두 개의 모듈이 사용되어 문제를 해결했는데 한 가지는 해당 자리에 퀸을 놓을 수 있는지 판단하는 check 함수, 그리고 다른 하나는 재귀적으로 n개의 자리를 선택하는 dfs 함수입니다.

 

기본적으로 열을 기준으로 한 열마다 퀸을 하나씩 배치하면서 n개의 열을 모두 채우는 로직을 구현하고 있기 때문에 check함수에서는 해당 열의 특정 행에 놓을 수 있는지 판단하기 위해서 이전 열들을 검사합니다. 여기서 전체 영역을 계산하는 대신 퀸의 이동 범위를 고려하여 직선과 위아래 대각선의 3방향만을 체크하여 가능 여부를 판단합니다.

 

dfs에서는 각 열마다 인덱스 0부터 N-1행에 퀸을 놓을 수 있는지 check함수를 통해 검사하고 놓을 수 있는 경우 다음 단계로 보냅니다. 이 때 모든 경우의 수를 체크하기 위해 dfs를 재귀호출한 이후 퀸을 놓았다는 표시를 다시 제거합니다. 이런 구성을 취할 경우 중간에 막히게 되면 5행에 놓았다고 가정했을 때 5행의 표시를 지우고 다음 6행으로 나아가는 식으로 작동하며 만약 마지막 행까지 불가능하다면 이전 열에서 선택했던 것의 다음 행을 판단하는 식으로 가능한 경우만 선택적으로 판단할 수 있게 됩니다.

 

dfs를 돌면서 모든 퀸을 놓은 경우인 n이 N과 같을 때만 카운팅을 해주면 답을 얻을 수 있습니다.

 

⏱ 시간 복잡도

처음 N개를 선택하고 다음 열에서 N-1개를 선택하는 식으로 생각하면 최악의 경우 O(N!)이 가능하지만 실제로는 백트랙킹에 의해 많은 경우의 수가 제거됩니다. 실제로 어느 정도인지 계산하는 것은 매우 어렵기 때문에 적당한 크기의 테스트 케이스의 실행 속도로 판단해보는 편이 좋습니다.

 

💻 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	
	static int N;
	static int res;
	static boolean[][] board;
	
	static boolean check(int r, int c) {
		int j = c-1, cnt = 1;
		while(j >= 0) {
			if(board[r][j]) {
				return false;
			}
			if(r-cnt >=0 && board[r-cnt][j]) {
				return false;
			}
			if(r+cnt < N && board[r+cnt][j]) {
				return false;
			}
			j--;
			cnt++;
		}
		return true;
	}

	static void dfs(int n) {
		if(n == N) {
			res++;
			return;
		}
		for(int i=0;i<N;i++) {
			if(!check(i, n)) {
				continue;
			}
			board[i][n] = true;
			dfs(n+1);
			board[i][n] = false;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		res = 0;
		board = new boolean[N][N];
		dfs(0);
		System.out.println(res);
		br.close();
	}
}