[백준 9663/Java] N-Queen

문제

---

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

9663번: N-Queen

 

풀이 과정

---

이 문제를 해결하기 위해 백트래킹 기법을 사용하였습니다.

백트래킹(Backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 의미한다. 최적화 문제와 결정 문제를 푸는 방법이 된다.

check_col 함수를 통해 같은 행에 퀸이 있는지를 체크하고, check_diagonal 함수를 통해 대각선에 퀸이 배치되어 있는지를 먼저 체크한 뒤, 둘 다 퀸이 없다면 현재 위치에 퀸을 배치합니다.

그다음 y값에 1을 더해 다음 행으로 이동합니다. 여기서 y는 행을 의미하고 x는 열을 의미합니다.

다음 행으로 이동한 뒤, x값을 다시 0부터 시작하여 알맞은 위치에 배치하고 다음 행으로 이동하고를 반복합니다.

public class N_Queen {
	
	static int board[][];
	static int N;
	static int answer = 0;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		board = new int[N][N];
		NQueen(0);
		System.out.println(answer);
	}
	
	public static void NQueen(int y) {
		if(y == N) { //마지막 퀸까지 배치가 되었다면, answer++
			answer++;
			return;
		}
			
		for(int x=0; x<N; x++) { //x는 row값을 의미하며 y는 column값을 의미
			if(check_col(x, y) && check_diagonal(x, y)) { //같은 행과 대각선에 퀸이 없다면
				board[y][x] = 1; //현재 위치에 퀸을 배치
				NQueen(y + 1);   //다음 행으로 이동
				board[y][x] = 0; //퀸을 보드에서 제거
			}
		}
	}
	
	public static boolean check_col(int x, int y) {
		for(int i=y; i<N; i++) {
			if(board[i][x] == 1)
				return false;
		}
		for(int i=y; i>=0; i--) {
			if(board[i][x] == 1)
				return false;
		}
		return true;
	}
	
	public static boolean check_diagonal(int x, int y) {
		int tmpX = x;
		int tmpY = y;
		do { //왼쪽 위 대각선 체크
			if(board[tmpY][tmpX] == 1)
				return false;
			tmpX--; tmpY--;
		} while(tmpX >= 0 && tmpY >= 0);
		
		tmpX = x;
		tmpY = y;
		do { //왼쪽 아래 대각선 체크
			if(board[tmpY][tmpX] == 1)
				return false;
			tmpX--; tmpY++;
		} while(tmpX >= 0 && tmpY < N);
		
		tmpX = x;
		tmpY = y;
		do { //오른쪽 위 대각선 체크
			if(board[tmpY][tmpX] == 1)
				return false;
			tmpX++; tmpY--;
		} while(tmpX < N && tmpY >= 0);
		
		do { //오른쪽 아래 대각선 체크
			if(board[y][x] == 1)
				return false;
			x++; y++;
		} while(x < N && y < N);
		return true;
	}
}

탐색 과정이 많아 N값이 커질수록 출력 시간이 기하급수적으로 늘어났습니다. 출력은 아래와 같습니다.

N(1~14) ->  (1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596)

저는 2차원 배열을 사용하여 문제를 풀었지만, 1차원 배열로도 가능하다고 합니다.

각 원소의 index를 '열'이라 생각하고, 원소 값을 '행'이라 생각하여 풀 수도 있습니다!