[프로그래머스 lv2] N-Queen 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

Queen 들을 배치하기 전 알아두면 좋은 사항들이 있다.

 

1. Queen은 한 행에 하나씩만 위치한다.

: 같은 행에 두 개 이상의 Queen이 있으면 서로를 공격할 수 있기 때문이다.

: 따라서, 우리는 0행부터 n-1행까지의 퀸에 대해 열만 결정하면 된다.

 

2. Queen의 열의 결정할 때 고려해야 할 사항은 세 가지이다.

(1) 이전에 선택했던 열을 재선택할 수 없다.

: 같은 열에 두 개 이상의 Queen이 있으면 서로를 공격하기 때문이다.

 

(2) 이전에 선택한 좌표가 공격할 수 있는 오른쪽 대각선을 피해야 한다.

: 같은 대각선에 두 개 이상의 Queen이 있으면 서로를 공격하기 때문이다.

: 이전에 선택한 퀸 좌표가 (x, y)라고 할 때, 해당 퀸이 공격할 수 있는 대각선 라인은 두 좌표의 합이 x+y인 좌표들이다.

: 따라서, 이전에 선택한 퀸 좌표의 행+열 값을 기록해놓고, 이후에는 행+열의 값이 동일한 좌표를 선택하지 않아야 한다.

 

(3) 이전에 선택한 좌표가 공격할 수 있는 왼쪽 대각선을 피해야 한다.

: 같은 대각선에 두 개 이상의 Queen이 있으면 서로를 공격하기 때문이다.

: 이전에 선택한 퀸 좌표가 (x, y) 라고 할 때, 해당 퀸이 공격할 수 있는 대각선 라인은 두 좌표의 차가 x-y인 좌표들이다.

: 따라서, 이전에 선택한 퀸 좌표의 행-열 값을 기록해놓고, 이후에는 행-열 값이 동일한 좌표를 선택하지 않아야 한다.

 

선택한 열(check1), 선택한 오른쪽 대각선(check2), 선택한 왼쪽 대각선(check3)을 기록하면서 재귀 함수로 0번 행부터 n-1번 행을 결정하자. n-1번 행까지 모두 결정되었을 때 가능한 경우의 수(cnt)를 1 증가시킨다. 최종 cnt 값을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

void func(int k, int& cnt, vector<bool>& check1, vector<bool>& check2, vector<bool>& check3, int n) {

    if (k >= n) {
        cnt++;
        return ;
    }

    for (int i=0; i<n; i++) {
        if (check1[i]) continue;
        if (check2[k+i]) continue;
        if (check3[k-i+(n-1)]) continue;
        check1[i] = true;
        check2[k+i] = true;
        check3[k-i+(n-1)] = true;
        func(k+1, cnt, check1, check2, check3, n);
        check1[i] = false;
        check2[k+i] = false;
        check3[k-i+(n-1)] = false;
    }
}

int solution(int n) {

    vector<bool> check1(n, false);
    vector<bool> check2(2*n, false);
    vector<bool> check3(2*n, false);

    int cnt = 0;
    func(0, cnt, check1, check2, check3, n);
    return cnt;
}