[BOJ 백준] N-Queen(9663) C++

 

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

9663번: N-Queen

 

 

문제 설명 : 

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

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

 

입력 : 

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

출력 : 

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

 

예제 입력 : 

8

예제 출력 : 

92

 

 

접근법 : 

1) 어떻게 풀 것인가?

힌트

① Queen의 이동경로

* 아이디어 :

   - 각 행에 가능한 최대 퀸의 개수는 1개다 

   - 각 열에 가능한 최대 퀸의 개수는 1개다

 

→ 행을 지나면서 DFS를 수행하면 어떨까?

 

 

 

② dfs를 진행할 경우 가능한 backtracking 경우의 수 3가지

 

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

Java 코드 : 

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

public class Main {
	
	static int[] xLocation = new int[16];
	static int N, ans;
		
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
		N = Integer.parseInt(br.readLine());
		ans = 0;
		
		nQueen(0);

		bw.write(String.valueOf(ans));
		
        br.close();
        bw.close();
        return;
	}
	
	static void nQueen(int y) {
		if (y==N) {
			ans++;
			return;
		}
		
		// i 행 j 열
		for (int j = 0; j < N; j++) {
			boolean isPossible = true;
			for (int i = 0; i < y; i++) {
				// 안되는 모든 경우의 수
				// 1) 같은 열에 존재하는 경우
				if ( xLocation[i]==j || 
					
					// 2) ↖  위 대각선 ↖ 에 존재하는 경우
						( xLocation[i] - (y-i) == j ) ||
					// 3) ↗ 오른쪽 위 대각선 ↗ 에 존재하는 경우
						( xLocation[i] + (y-i) == j ) ) {
					isPossible = false;
					break;
				}	
					
			}
			if (isPossible) {
				xLocation[y] = j;
				nQueen(y+1);
			}
		}
	}
}

 

C++ 코드 : 

// N-Queen 9663 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#define ABS(a) ((a)>0? (a) : (-a))

using namespace std;

int N;							
int ans;						// ans : 정답

int xLocation[16];

void nQueen(int y);

int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	scanf("%d", &N);

	// 2. NQueen 수행
	nQueen(0);

	// 3. 답을 출력한다
	printf("%d", ans);
	return 0;
}

void nQueen(int y) {
	// 마지막 줄이면 무조건 queen 놓으면서 마무리
	if (y == N) {
		ans++;
		return;
	}

	// i : 행 / j : 열
	for (int j = 0; j < N; j++) {
		bool isPossible = true;
		for (int i = 0; i < y; i++) {
			// 안되는 모든 경우의 수
			// 1) 같은 열에 존재하는 경우
			if (xLocation[i] == j  ||
			// 2) 왼쪽 위 대각선에 존재하는경우
				 (xLocation[i] - (y-i)) == j ||
			// 3) 오른쪽 위 대각선이 존재하는 경우 
				(xLocation[i] + (y - i)) == j
				) {
				
				isPossible = false;
				break;

			}
		}
		if (isPossible) {
			xLocation[y] = j;
			nQueen(y + 1);
		}
		
	}
}
#endif