프로그래머스_NQueen

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

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

풀이 1. 순열을 사용하기

처음 순열을 사용할 때는 해당 순열을 돌려가면서 실제 대각선 위치를 전부 계산하여 값을 구했는데

이는 굉장히 비효율적임을 깨달았다(실제 효율성도 아쉬웠다)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool check_queen(vector<int> q, int n){
    vector<int> qe(n);
    // 각 행*n + 열 값 갱신
    for(int i=0;i<n;i++)
        qe[i] = q[i]+(n*i); 
    
    // 겹치는지 확인(대각선 오른쪽)
    for(int i=0;i<n;i++){
        // 최대한 상좌 방향으로 올려서 검사
        int dig = qe[i];
        while(dig%n!=1 && dig>n){
            dig = dig -(n+1);
        }
        // 다른 것과 비교
        while(true){
            for(int j=0;j<n;j++){
                // 동수 제외
                if(i==j)    continue;
                if(dig == qe[j])
                    return false;
            }
            // 대각선 이동(하우)
            if(dig%n==0 || dig > n*(n-1))
                break;
            dig = dig+n+1;
        }
    }
    // 겹치는지 확인(대각선 왼쪽)
    for(int i=0;i<n;i++){
        // 최대한 상우 방향으로 올려서 검사
        int dig = qe[i];
        while(dig%n!=0 && dig>n){
            dig = dig -n +1;
        }
        // 다른 것과 비교
        while(true){
            for(int j=0;j<n;j++){
                // 동수 제외
                if(i==j)    continue;
                if(dig == qe[j])
                    return false;
            }
            // 대각선 이동(하좌)
            if(dig%n==1 || dig > n*(n-1))
                break;
            dig = dig+n-1;
        }
    }
    return true;
}

int solution(int n) {
    int answer = 0;
    
    // 기본 행 기준, 열값을 넣도록
    // 순열 1~N 만들기
    vector<int> q(n);
    for(int i=0;i<n;i++)
        q[i]=i+1;

    // 확인
    do{
        if(check_queen(q,n))
            answer++;
    }while(next_permutation(q.begin(), q.end()));
    
    return answer;
}

 

풀이 2. 순열을 사용하기(연산 최소화)

연산을 최소화하여 보다 깔끔한 코드가 되었지만 그럼에도 불구하고 순열을 사용하는 것 자체가 부담임을 깨달았다.

N이 12로 주어졌을 때, 12개의 순열을 전부 돌린다 생각해보면 끔찍하다.

(실제 채점결과도 90.9점 이었다)

#include <string>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

bool check_queen(vector<int> q, int n){
    for(int i=0;i<n;i++){
        // 대각선 같으면
        for(int j=0;j<n;j++){
            if(i==j) continue;
            if(abs(q[i]-q[j]) == abs(i-j))
                return false;
        }
    }
    return true;
}

int solution(int n) {
    int answer = 0;
    
    // 기본 행 기준, 열값을 넣도록
    // 순열 1~N 만들기
    vector<int> q(n);
    for(int i=0;i<n;i++)
        q[i]=i;

    // 확인
    do{
        if(check_queen(q,n))
            answer++;
    }while(next_permutation(q.begin(), q.end()));
    
    return answer;
}​

풀이 3. 백트랙킹

순열로 풀어보려고 했으나, 순열로 접근하는 것 자체가 시간을 많이 잡아먹는다는 것을 깨닫고 

순열보다 정석적인 풀이인 백트랙킹으로 해결하였다.

#include <string>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;
int answer_cp=0;

bool check_queen(vector<int> q, int idx){
    // 열과 대각선 체크
    for(int i=0;i<idx;i++){
        if(q[i]==q[idx]) return false;
        if(abs(q[i]-q[idx]) == abs(i-idx)) return false;
    }
    return true;
}

void make_queen(vector<int> q, int cnt){
    if(cnt == q.size()){
        answer_cp++; // 정답 증가
        return;
    }
    for(int i=0;i<q.size();i++){
        q[cnt]=i;
        if(check_queen(q, cnt))
            make_queen(q,cnt+1);
    }
}

int solution(int n) {
    int answer = 0;
    vector<int> q(n);
    make_queen(q,0);
    answer=answer_cp;
    return answer;
}