[Java+Python]9663번, N-Queen

문제

 

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

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

출력

 

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

풀이

 

이전 풀이는 가장 왼쪽 위칸에 퀸이 놓이는지 놓이지 않는지에 따라

 

가능한 전체 경우의 수를 구하는 방법이었다.

 

어떻게든 통과하긴 했지만, 시간복잡도도 매우 컸고 무엇보다 코드가 난잡해져서..

 

메서드에 전달되는 매개변수를 가능한 줄이면서도 이해하고 외우기 쉬운 코드를 목표로 새로 작성해 보았다.

 

로직은 대략 다음과 같다.

 

1. 0번 row로 시작해 dfs를 실행한다.
2. row가 주어진 N과 같으면 result의 값을 1 증가시키고 재귀를 종료한다.
3. 그렇지 않다면, 0부터 n - 1까지 반복문을 돌며 해당 row에 퀸을 놓을 수 있는 column을 골라 depth + 1을 탐색한다.
4. 여기서 같은 행과 열, 그리고 대각선에 퀸이 놓여있지 않다면 퀸을 놓을 수 있는 column이라 판단한다.

그다지 어렵지 않은 로직이지만, 문제의 조건에 주어졌듯이 15를 넘어가면 시간이 아주 많이 소요된다.

 

그도 그럴 수밖에 없는 것이, 사실상 N x N 체스판의 모든 칸을 순회하며 가능한지 여부를 따져보기 때문에

 

시간복잡도가 O(N!)이기 때문이다.

 

그래도 이전 구현보다는 시간을 절반을 줄여서 만족.

 

하지만 파이썬은 아무리 해도 통과가 되지 않아 pypy3으로 만족하기로 했다(...).

 

먼저 자바 코드.

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

public class Prob9663 {

	static int n;
	static int result;
	static int[] column;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		column = new int[n];

		dfs(0);

		System.out.println(result);
	}

	static void dfs(int depth) {

		if (depth == n) {
			result++;
			return;
		}

		for (int i = 0; i < n; i++) {
			column[depth] = i;
			if (isPossible(depth)) {
				dfs(depth + 1);
			}
		}
	}

	static boolean isPossible(int depth) {
		for (int i = 0; i < depth; i++) {
			if (column[i] == column[depth] || Math.abs(column[depth] - column[i]) == depth - i) {
				return false;
			}
		}
		return true;
	}
}

다음으로 파이썬 코드이다.

import sys

n = int(sys.stdin.readline().rstrip())
result = 0
column = [0 for _ in range(n)]


def isPossible(depth):
    for i in range(depth):
        if column[i] == column[depth] or abs(column[depth] - column[i]) == depth - i:
            return False
    return True


def dfs(depth):
    global result

    if depth == n:
        result += 1
        return

    for i in range(n):
        column[depth] = i
        if isPossible(depth):
            dfs(depth + 1)


dfs(0)

print(result)