프로그래머스 : N-Queen (C++, Lv.3, 백트래킹)

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

코딩테스트 연습 - N-Queen

학부시절 인공지능 수업에서 한 번 다뤄봤던 문제여서 이해하는 데에는 쉬웠다.

근데 어떻게 대각선의 범위를 정해야 하는가가 첫 고민이었고 해당 좌표에 두지 못한다고 체크를 어떻게 해야 하는지가 두 번째 고민이었다.

첫 번째 고민의 경우 해당 좌표의 아래 depth에 해당하는 좌표들에 대해서만 체크 표시를 했다. (23~35line)

현재 depth 별로 퀸을 두는 코드이기 때문에 아래 퀸을 윗 퀸보다 먼저 둘 수 없으므로 굳이 생각하지 않아도 된다.

 

두 번째 고민의 경우 원래는 ch[][] 를 1로 바꾸거나 해제 할 때 0으로 바꾸는 로직으로 짰는데 그러면 두지 않아야 할 자리도 0으로 초기화되길래 ++, --를 이용해 ch[][] 가 0 인 좌표에만 두도록 설계했다.

푸는데 좀 오래 걸렸다 ㅜㅜ

 

소스코드

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

int N;
int answer;
int ch[13][13];
int a,b;
void dfs(int depth) {
    if(depth == N) {
        answer++;
        return;
    }
    
    for(int i =0 ; i <N ; i++) {
        //이미 방문한 곳이면 걍 넘기기
        if(ch[depth][i]) continue;
        ch[depth][i]++;
        //세로 배열 체크
        for(int k = 0; k < N ; k++) ch[k][i]++;
        //가로 배열 체크
        for(int k = 0; k < N ; k++) ch[depth][k]++;
        // \대각선 배열 체크
        a = depth+1; b = i+1;
        while(a<N && b< N) {
            ch[a][b]++;
            a++; b++;
        }
        // /대각선 배열 체크
        a = depth+1; b = i-1;
        while(a<N && b >= 0) {
            ch[a][b]++;
            a++; b--;
        }
        
        //dfs 실행
        dfs(depth+1);
        
        ch[depth][i]--;
        //세로 배열 체크 해제
        for(int k = 0; k < N ; k++) ch[k][i]--;
        //가로 배열 체크
        for(int k = 0; k < N ; k++) ch[depth][k]--;
        // \ 대각선 배열 체크 해제
        a = depth+1; b = i+1;
        while(a<N && b< N) {
            ch[a][b]--;
            a++; b++;
        }
        // / 대각선 베얄 체크 해제
        a = depth+1; b = i-1;
        while(a<N && b >= 0) {
            ch[a][b]--;
            a++; b--;
        }
    }
}
 
int solution(int n) {
    N = n;
    
    dfs(0);
    
    
    return answer;
}