BOJ 9663번: N-Queen

문제

문제 바로가기> BOJ 9663번: N-Queen

9663번: N-Queen

 

풀이

`board[row] = col` 값을 저장하여, 2차원 배열이 아닌 1차원 배열로 문제를 해결할 수 있다.

 

퀸을 놓을 때 가로, 세로, 대각선을 확인해야 하는데,

solution() 함수에서 한 줄에 하나를 놓고,

유망한 경우, 다음 solution을 호출하기 때문에 자동으로 한 row에는 퀸이 하나만 놓인다.

따라서 대각선과 동일한 column에 퀸이 놓여 있는지를 통해 해당 위치가 유망한지 판단해주면 된다.

 

C++

#include<iostream>
#define MAX 16
using namespace std;

int N, ans=0;
int board[MAX];

bool promising(int row) {
	for (int i = 1; i < row; i++) {
		if (board[i] == board[row] || row - i == abs(board[row] - board[i])) return false;
	} return true;
}

void solution(int row) {
	if (row == N+1) {
		ans++;
		return;
	}
	for (int col = 1; col <= N; col++) {
		board[row] = col; // 말을 놓아 봄 
		if (promising(row)) solution(row +1); // 유망한 경우 계속 
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	solution(1);
	cout << ans;
}

 

Java

import java.io.*;
import java.util.*;

public class Main {
	
	static int N, ans=0;
	static int[] board;

	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		board = new int[N+1];
		solution(1);
		System.out.println(ans);
	}

	static void solution(int row) {
		if(row == N+1) {
			ans++;
			return;
		}
		for(int col=1; col<=N; col++) {
			board[row] = col;
			if(promising(row)) solution(row+1);
		}
	}

	static boolean promising(int row) {
		for(int r=1; r<row; r++) {
			if(board[row] == board[r] || row-r == Math.abs(board[row]-board[r])) return false;
		} return true;
	}
}