[프로그래머스] N-Queen - C++

문제

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

 

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

 

입출력 예

n	result
4	2

---

기본 아이디어

N-Queen은 진짜 유명한 백트래킹 문제임

 

4 X 4 체스판에서 4개의 퀸을 서로 공격 범위가 겹치지 않게 두기 위해

(0, 0)부터 첫번째 퀸을 배치해 나가본다고 가정한다.

그렇게 되면

 

 

두번째 퀸을 (1, 2)에 배치하고, 마지막 남는 칸인 (3, 1)에 세번째 퀸을 배치하고 나면

마지막 퀸을 배치할 수 있는 방법이 존재하지 않는다.

 

 

 

따라서 다시 두번째 퀸으로 돌아와 두번째 퀸을 (1, 3)에 배치한다고 가정한다.

 

그러나 세번째 퀸을 (2, 1)에 배치하고 나면 마지막 퀸을 배치할 수 있는 방법이 사라지기 때문에

 

 

다시 첫번째 퀸으로 돌아와 첫번째 퀸을 (0, 1)에 배치한다.

 

두번째 퀸을 (1, 3), 세번째 퀸을 (2, 0), 마지막 퀸을 (3, 2)에 배치하면 총 네 개의 퀸을 배치할 수 있게 된다.

 

이와 같은 방법으로 첫번째 퀸을 (0, 2)에 배치하면

 

마찬가지로 2, 3, 4번째 퀸의 위치를 따라 배정해주게 되면 네개의 퀸이 모두 배치가 가능하다.

 

 

이 과정을 DFS 기반의 백트래킹에 적용하게 되면 다음과 같다.

 

1. 어차피 퀸은 한 행에 하나밖에 못 들어간다. (공격범위로 인해)

    → 각 queen마다 (0 ~ N - 1) 까지 들어갈 수 있는 column만 탐색

 

2. 만약 i번째 column에 들어갈 수 있으면

visited[queen][i] = true; // 현재 탐색중인 퀸을 (queen, i)에 두고
DFS(queen + 1) // 다음 queen 탐색
visited[queen][i] = false;
// 전체 경우의 수 탐색을 위해
// (queen, i)에 배치해두는 경우가 종료되면 false로 되돌려놓기

 

이 때, 다른 퀸과 공격이 가능한지 여부를 판단하여 각 column 별 방문 가능 여부를 결정한다.

퀸의 공격 범위는 같은 행 / 같은 열 / 양 대각 방향 인데, 각 row 별로 하나씩만 배치하기 때문에 이미 동일 행 범위는 탐색이 끝났고,

 

- 같은 column에 queen이 존재하는 경우

for(i = 0; i < N; i++) {
    if(i != row && visited[i][col]) return false;
}

 

- 양 대각선 방향에 존재하는 경우

// 대각선 방향 체크
int l_r_diag = row - col;
int r_l_diag = row + col;

for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
        if((i - j == l_r_diag || i + j == r_l_diag) && visited[i][j]) return false;
    }
}

원리

 

와 같이 계산해주어 방문 여부를 판단하면 된다.

 

코드 - 1

#include <string> 
#include <vector>

#define MAX 13

using namespace std;

bool visited[MAX][MAX] = { false };
int N, cnt = 0;

bool is_placed(int row, int col) {
    // 행 방향 체크
    for(int i = 0; i < N; i++) {
        if(i != row && visited[i][col]) return false;
    }
    
    // 대각선 방향 체크
    int l_r_diag = row - col;
    int r_l_diag = row + col;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if((i - j == l_r_diag || i + j == r_l_diag) && visited[i][j]) return false;
        }
    }
    return true;
}

void DFS(int queen) {
    if(queen == N) {
        cnt++;
        return;
    }

    for(int i = 0; i < N; i++) {
        if(is_placed(queen, i)) {
            visited[queen][i] = true;
            DFS(queen + 1);
            visited[queen][i] = false;
        }
    }

}


int solution(int n) {
    N = n;
    DFS(0);
    return cnt;
}

 

 

까지가 가장 단순한 풀이 방법이고,

동일 원리를 활용했을 때 좀 더 효율적인 풀이 방법은 다음과 같다.

 

응용 풀이

어차피 퀸은 한 행에 하나밖에 못 들어간다.
- 아까 내가말함

 

따라서 bool visited[N][N] 대신,

int visited[queen] 에 queen번째 퀸이 들어갈 수 있는 column을 저장해주면 된다.

 

원리는 동일하기 때문에 DFS 부분의 코드는 크게 수정해줄 것이 없고,

방문 여부만 조금 다르게 생각하면 된다.

 

마찬가지로 같은 행에 존재하는 경우는 이미 고려를 했기 때문에 넘어가고,

- 같은 column에 queen이 존재하는 경우

for(int i = 0; i < queen; i++)
    if(visited[queen] == visited[i]) return false;

이와 같이 판단해주면 된다.

또한, 어차피 queen은 0부터 N까지 순차적으로 탐색을 해주기 때문에 현재 존재하는 queen 위에까지만 탐색을 진행하여 해당 범위에 걸리는 queen이 있는지만 판단해준다.

 

- 양 대각선 방향에 존재하는 경우

for(int i = 0; i < queen; i++) {
    if(queen - i == abs(visited[queen] - visited[i])) return false;
}

원리는 위와 조금은 다른데,

이와 같이 양 대각 방향에 queen이 존재하는지 여부를 구해준다.

 

따라서 수정한 코드는 다음과 같다.

 

코드 - 2

#include <string> 
#include <vector>

#define MAX 13

using namespace std;

int visited[MAX] = { 0 };
int N;
int answer = 0;

bool is_placed(int queen) {
    for(int i = 0; i < queen; i++) { // 0부터 현재 queen 위로만 탐색 진행
        if(visited[i] == visited[queen] || queen - i == abs(visited[queen] - visited[i])) return false;
    }
    return true;
}

void DFS(int queen) {
    if(queen == N) {
        answer++;
        return;
    }

    for(int i = 0; i < N; i++) {
        visited[queen] = i;
        if(is_placed(queen)) {
            DFS(queen + 1);
        }
    }
}

int solution(int n) {
    N = n;
    DFS(0);
    return answer;
}