[Python/Java] 백준 9663번 - N-Queen (골드 4)

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 브루트포스 알고리즘
 - 백트래킹

 

 

문제

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

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

입력

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

출력

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

 

---

 

처음에는 NxN칸의 체스판에 최대 몇 개의 퀸을 놓을 수 있는 건지 확인하는 줄 알고 잘못 풀었다...

 

예제를보니 N=8일 때 92여서 아.. 잘못 풀었구나 하고 다시 확인하였다.

 

N x N칸의 체스판에서 N개의 퀸을 놓을 수 있는 모든 경우의 수를 찾는 문제였다.

 

 

N = 1일 때

1 x 1칸의 체스판에 1개의 퀸을 놓을 수 있기 때문에

경우의 수는 1

 

N = 2일 때

2 x 2칸의 체스판에 2개의 퀸을놓아야 하는데

보시다시피 1칸이라도 퀸을 놓는다면 나머지 칸에는 둘 수 없기 때문에

경우의 수는 0

 

N = 3일 때

3 x 3칸의 체스판에 3개의 퀸을놓아야 하는데

어디에 두던지 간에 2개밖에 놓지 못하기 때문에

경우의 수는 0

  

N = 4일 때는

위의 두가지 그림을 보면 첫 번째 칸에 퀸을 놓을 경우 최대 3개의 퀸밖에 놓지 못하는 것을 확인할 수 있다.

 

하지만 밑의 두 그림을 보면

 

두 번째 칸과 세 번째 칸에 퀸을놓을 경우 4개의 퀸을 놓을 수 있는 것을 확인할 수 있다.

 

이제 이 사실을 가지고 문제를 풀 수 있다.

 

 처음에는 2차원 배열을 이용하여 풀려 하였으나 이내 알 수 있었다.

 

하나의 행 혹은 열에는 하나의 퀸만 올 수 있다는 것을.

 

그럼 1차원 배열을 통해 각 열마다 어디 행에 퀸이 위치하는지를 기록하여 퀸이 놓일 수 있는 곳을 알 수 있다.

 

Java 코드

import java.io.*;
import java.util.StringTokenizer;
import java.util.PriorityQueue;

public class Main {
	static int n = 0;
	static int [] board;
	static int result = 0;
  public static void main(String[] args) throws IOException {
	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	  n = Integer.parseInt(br.readLine());
	  
	  board = new int[n];
	  dfs(0);
	  System.out.print(result);
  }
  
	private static void dfs(int idx) {
		if(idx == n) {
			result++;
			return;
		}
		
		for(int i=0; i<n; i++) {
			board[idx] = i;
			if(check(idx)) {
				dfs(idx+1);
			}
		}
	}
	
	private static boolean check(int idx) {
		for(int i=0; i<idx; i++) {
			if(board[i] == board[idx] || Math.abs(i-idx) == Math.abs(board[i] - board[idx])) {
				return false;
			}
		}
		
		return true;
	}

}

 

Python 코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())

board = [0] * n
result = 0

def check(idx):
    for i in range(idx):
        if board[i] == board[idx] or abs(i-idx) == abs(board[i] - board[idx]):
            return False
    return True

def dfs(idx):
    global result
    
    if idx == n:
        result += 1
        return
    
    for i in range(n):
        board[idx] = i
        if check(idx):
            dfs(idx+1)

dfs(0)
print(result)

참고로 파이썬으로 제출 할 경우 시간초과, PyPy3로 제출하면 메모리 초과가 발생한다.

 

파이썬으로 풀기에는 상당히 빡빡한 문제였다.

 

---

1차원 배열로 푸는 원리는 앞선 N = 4일 때를 경우로 확인할 수 있다.

 

앞선 코드에서

 

if board[i] == board[idx] or abs(i-idx) == abs(board[i] - board[idx]):

이 부분이 위의 1차원 배열을 확인하는 코드이다.

 

if board[i] == board[idx]:

i와 idx가 같은 값, 즉 같은 열이면 놓을 수 없다.

 

if abs(i-idx) == abs(board[i] - board[idx]):

 행 - 행 == 열 - 열

 

즉, 대각선이면 놓을 수 없다.