[프로그래머스] Level 2. N-Queen

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

프로그래머스

 

 

해결 방법(실패)

• 완전탐색을 진행하면서, 퀸을 놓는다. 
• is_valid() 함수를 놓아서 현재 자리에  퀸을 놓을수 있는지 없는지 검사한다.
• 만약 퀸 개수가 n개까지 놓였다면 answer ++ 를 하고 다음검사를 진행한다.

이 방법은 마지막 두 문제에서 시간초과가 발생했다. 

#include <string>
#include <vector>
#include <unordered_set>
#include <iostream>

using namespace std;

unordered_set<int> queens;
int max_queen =0;
int answer = 0;

bool is_valid(int i, int j){
   
    for(auto it = queens.begin(); it  != queens.end(); it++){
        int qi = *it/100; int qj = *it%100;
        int gapi = qi < i ? i-qi : qi -i;
        int gapj = qj < j ? j -qj : qj - j;
        if(gapi== 0 || gapj==0 || gapi == gapj) return false;
    }
    
    return true;
}

void go_search(int i, int j){
    if(queens.size() == max_queen){
        answer ++;
        continue;
    }
    
    for(; i<max_queen; i++){
        for(; j<max_queen; j++){
            if(!is_valid(i,j)) continue;
            
            queens.insert(i*100+j);
            
            go_search(j+1==max_queen ? i+1 : i, j+1 == max_queen ? 0:j+1);
            queens.erase(i*100+j);
        }
        j=0;
    }
}

int solution(int n) {
    
    max_queen = n;    
    go_search(0,0);
    return answer;
}

 

 

해결방법(성공)

어차피 한 행에 하나의 말만 놓을 수 있으므로, 각 행마다 몇번째 열에 말을 놓을것인지를 검사한다.

퀸을 놓음에 따라 놓을 수 없는 열, 대각선이 생긴다. 이것을 각각 vector에 넣어놓고 불필요한 검사를 패스할 수 있도록 한다. 

 

#include <vector>
#include <iostream>

using namespace std;

int max_queen = 0;
int answer = 0;

// 열과 대각선 사용 여부를 기록하는 배열
vector<bool> col_used;   // 열 사용 여부
vector<bool> diag1_used; // ↘ (좌상단 -> 우하단) 대각선 사용 여부
vector<bool> diag2_used; // ↙ (우상단 -> 좌하단) 대각선 사용 여부

void go_search(int row) {
    if (row == max_queen) { // 모든 행에 퀸을 배치 완료
        answer++;
        return;
    }

    for (int j = 0; j < max_queen; j++) {
        if (col_used[j] || diag1_used[row + j] || diag2_used[row - j + max_queen - 1]) continue;

        // 현재 위치에 퀸 배치
        col_used[j] = diag1_used[row + j] = diag2_used[row - j + max_queen - 1] = true;

        go_search(row + 1); // 다음 행으로 이동

        // 원래 상태로 복구 (백트래킹)
        col_used[j] = diag1_used[row + j] = diag2_used[row - j + max_queen - 1] = false;
    }
}

int solution(int n) {
    max_queen = n;
    answer = 0;

    col_used.assign(n, false);
    diag1_used.assign(2 * n - 1, false);
    diag2_used.assign(2 * n - 1, false);

    go_search(0);
    return answer;
}