백준 9663번 <N-Queen>

백준 알고리즘 9633번

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

9663번: N-Queen

9633번

퀸 N개를 서로 공격할 수 없게 놓을 수 있는 경우의 수를 구하여라.

 

입력으로 퀸의 개수 N이 들어온다.

 

출력은 퀸 N개가 서로 공격할 수 없게 되는 경우의 수를 구해서 출력하면 된다.

 

문제 해결

각 행을 차례대로 확인하면서 각 열에 퀸을 놓는 경우를 고려한다.

이때 위쪽 행에 놓은 퀸을 고려하면서 현재 열에 놓을 수 있는지 확인한다.

0번째 행부터 0번 열부터 퀸을 놓는 경우부터 시작해서 조건에 맞도록 모든 퀸을 놓을 수 있는 경우를 카운트한다.

 

check함수는 퀸을 놓을 수 있는지 확인하는 함수이고,

dfs함수는 0번째 행의 0번 열에 퀸을 놓는 경우부터 시작해 모든 경우들을 확인하여 카운트하는 함수이다. 재귀함수로 구현되어 있다. 만약 dfs 함수의 인자로 들어오는 x값이 n과 같다면 모든 퀸을 놓았으므로 카운트를 하면 된다.

 

import java.util.Scanner;

public class Main9633 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] row = new int[n];
		System.out.println(dfs(row, 0));

	}

	public static boolean check(int[] row, int x) {
		for (int i = 0; i < x; i++) { 	// 이전 행에 대해 체크
			if (row[x] == row[i]) {  	// 세로로 겹치면 false
				return false;
			}
			if (row[x] - row[i] == x - i) {	// 대각선의 경우면 false
				return false;
			}
			if (-(row[x] - row[i]) == x - i) {
				return false;
			}
		}
		return true;
	}

	public static int dfs(int[] row, int x) {
		int result = 0;
		if (x == row.length) {
			result++;
		} else {
			for (int i = 0; i < row.length; i++) {	// 0번 열부터 n-1 열까지 
				row[x] = i;							// 퀸을 놓게 되는 경우들을 확인
				if (check(row, x)) {
					result += dfs(row, x+1);
				}
			}
		}
		return result;

	}

}

 

사실 엄청나게 많은 시간초과를 겪었는데 파이썬으로 코드를 구현해서 그랬다. 파이파이3가 더 빨라서 파이파이3로 제출해봤지만 그래도,, 시간초과였다.

파이썬이 인터프리터 언어이기 때문에 컴파일과 실행을 동시에 하기 때문에 더 느린 것 같아.

자바는 컴파일 언어로 컴파일을 하고나서 실행을 하기 때문에 실행시간은 적게 걸린다.