[프로그래머스] N-Queen

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

 

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

---

C++ 풀이

#include <string>
#include <vector>
using namespace std;

int answer;
int boardSize;

bool check(int h, int w, vector<vector<bool>> &chessBoard) { //퀸 배치가 가능한 위치인지 체크
	for (int i = 0; i < h; i++) { //세로 체크
		if (chessBoard[i][w] == true)
			return false;
	}
	int h1 = h - 1; int w1 = w - 1;
	while (h1 >= 0 && w1 >= 0) { //왼쪽 위 대각선 체크
		if (chessBoard[h1][w1] == true)
			return false;
		h1--; w1--;
	}
	while (h >= 0 && w <= boardSize) { //오른쪽 위 대각선 체크
		if (chessBoard[h][w] == true)
			return false;
		h--; w++;
	}
	return true;
}

void dfs(int currentN, vector<vector<bool>> chessBoard) {
	if (currentN == boardSize + 1) {
		answer++;
		return;
	}
	for (int i = 0; i <= boardSize; i++) {
		if (check(currentN, i, chessBoard)) {
			chessBoard[currentN][i] = true;
			dfs(currentN + 1, chessBoard);
			chessBoard[currentN][i] = false;
		}
	}
	return;
}

int solution(int n) {
	answer = 0;
	boardSize = n - 1;
	vector<vector<bool>> chessBoard(n, vector<bool>(n, false));
	dfs(0, chessBoard);
	return answer;
}

DFS로 풀었다.

 

 

 

 

 

 

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen | 프로그래머스