[프로그래머스]N-Queen(c++,c)

문제풀이:programmers.co.kr/learn/courses/30/lessons/12952?language=cpp

코딩테스트 연습 - N-Queen

 

n-queen 문제입니다.

아래 백준 문제와도 동일합니다.

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

9663번: N-Queen

gusdnr69.tistory.com/132

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

 

 

2차원배열이 아닌 1차원 배열로 구현할 수 있습니다.

 

1. row배열에 열값을 넣는다.

2. 넣으면 같은열에 있는 좌표가 있는지,

3. 대각선 상으로 일치하는 부분이 있는지 검사한다.

 

 

3가지 를 순서대로 구현해주면 되는 백트래킹 문제였습니다.

 

아래는 정답코드입니다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <cmath>
int N, result = 0;
int row[13] = { 0, }; //열값을 넣어줄 예정

bool checked(int r) {

	for (int i = 0; i < r; i++) {
		if (row[i] == row[r])
			return false;
		else if (abs(row[i] - row[r]) == r - i)
			return false;
	}
	return true;
}

void dfs(int r) {
	if (N == r) {
		result++;
		return;
	}

	for (int i = 0; i < N; i++) { //0열부터 n-1열까지 검사
		row[r] = i;
		if (checked(r)) {
			dfs(r + 1);
		}
		row[r] = 0;
	}
	return;
}

int solution(int n) {
	int answer = 0;
	N = n;
	dfs(0);
	answer = result;
	return answer;
}