c++ 프로그래머스_"N-Queen"

https://school.programmers.co.kr/learn/courses/30/lessons/12952?language=cpp 

프로그래머스

 

N-Queen 문제가 있길래

예전에 학교서 배운 알고리즘을 이해하고있나 싶어 풀어봤다.

​

일단 Queen 의 위치를 나타낼 배열을 생성해줬다.

문제 예시 첫번째 그림일 경우,

[ 3 , 1 , 4 , 2 ] 가 된다.

​

백트래킹을 사용해 DFS 하다가 유망하지않으면

더 DFS 하지 않고 다른 상태를 검사한다.

​

Queen의 위치를 보고 유망하지 않은지 판단한다.

 

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

예를 들어,

5x5 판에서

​

DFS를 돌아

현재 depth = 3 이고

3 위치의 [1] 에 Queen 을 넣었다고 가정하고

promising 판단을 해본다.

​

현재 위치(빨간색)에서 Queen의 움직일 수 있는 범위에 1 위치의 [3] 이 있다(연두)

abs(position[depth] - position[i]) == depth - i

abs(position[3] - position[1]) = 3 - 1

abs ( 1 - 3 ) = 2 = 3 - 1

if 조건에 부합한다.

(Queen이 닿는다)

유망하지 않으므로 return false,

​

​

​

다음 3 위치의 [2] 에 넣었을 경우

​

Queen 이 움직일 수 있는 범위에 아무 Queen(색칠된 칸)이 없다.

코드의 if 조건문에 해당되는 게 없어

(Queen이 닿는 곳이 없다)

이럴 경우 true를 반환하고 계속 진행한다.

​

계속 ....

​

 

이후 다 검사하고 다시 돌아와

그 다음 3 위치의 [3]과 비교하면 Queen의 범위에 있고

3 위치의 [4]를 비교하면

​

abs(position[3] - position[2]) = 3 - 2

abs(4 - 5 ) = 1 = 3 - 2

if 조건에 해당한다.

즉 Queen이 움직일 수 있는 범위에 해당되기 때문에

유망하지않아 그 다음은 DFS하지 않는다.

 

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

int answer = 0;
vector<int> position(13, 0);

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

void Queens(int n,int depth) {
	if (promising(depth)) {
		if (depth == n) {
			answer++;
		}
		else {
			for (int j = 1; j <= n; j++) {
				position[depth + 1] = j;
				Queens(n, depth + 1);
			}
		}
	}
}

int solution(int n) {
    
    Queens(n,0);

    return answer;
}

​