[프로그래머스 연습 문제] n퀸 c++ (백트래킹, dfs)

 

문제 링크

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

프로그래머스

 

문제풀이

이 문제는 dfs를 통한 완전탐색 과정에서, 백트래킹으로, 불가능한 트리의 가지를 가지치기 하여 수행 시간을 감소시켜야만 시간초과가 발생하지 않는다. 나는 이를 위해, 퀸이 8방향 모든 칸으로 이동하는 특성 중 좌, 우 모두 이동 가능한 특성을 활용하여 각 dfs(depth) 에서, depth 번째 행에 퀸을 놓을 수 있는 위치를 찾는 것으로 문제를 해결했다. 

 

퀸을 놓을 행은 1번 -> n번행으로 이동하고, 점점 아래 행으로 이동하기에, 퀸을 놓을 때 고려할 위치는 위의 3방향 뿐이다.

각 퀸을 특정 위치에 놓을 때마다 위 3방향에 이미 놓여진 퀸이 있는지 체크하고, 없다면 해당 위치에 퀸을 놓고 다음 행의 dfs로 재귀를 타면 된다. 

 

정답 코드

#include <string>
#include <vector>

using namespace std;
int visit[14][14];
int num;
int dw[3]={-1,-1,-1};
int dh[3]={-1,0,1};
int sum=0;
int cnt=20;
void dfs(int depth){
    if(depth==num){
            sum++;
            return;
    }
   
    for(int i=0;i<num;i++){
        if( visit[depth][i]==1)continue;
        
        bool possible=true
        for(int k=0;k<3;k++){ //위 3방향 중, 놓아진 퀸이 존재하는지 체크
             int nw=depth,nh=i;
            while(0<=nw&&nw<num&&0<=nh&&nh<num){
                if(visit[nw+=dw[k]][nh+=dh[k]]==1){
                    possible=false;
                    break;
                }
            } 
        }
        //위 세방향 모두 퀸이 존재하지 않는 경우만 해당 칸에 말을 놓고 진행
        if(!possible)continue; 
        visit[depth][i]=1;
        dfs(depth+1);
        visit[depth][i]=0;

    }
}


int solution(int n) {
    int answer = 0;
    num=n;
    dfs(0);
    return sum;
}

 

 

trouble  shooting

이때, 처음 시도한 방식은 각 퀸을 놓을 때마다, 아래 3방향에 visit 배열을 1로 만들어 해당 퀸의 모든 경로를 visit 표시하고, 해당 dfs 사이클 종료 후 다시 0으로 복구하는 방식을 사용했다. 하지만, 이 경우 역시 시간 초과가 발생했다.

그 이유는, 위 방식과 다르게, 각 퀸을 놓을 때마다, 모든 경로에 접근하여 visit[a][b]=1 표시를 하고, 해당 dfs 종료 시,

체크한 모든 visit에 대해 visit[a][b]=0 연산을 수행해야하기 때문이다.

위에 언급한 정답 방식을 사용하면 모든 경로에 visit을 체크하고 체크를 해제하는 작업이 필요 없기에, 훨씬 효율적인 방식이다.