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

N-Queen

문제 링크

N-Queen

분석

N * N 체스판 위에 N개의 퀸을 서로 공격하지 않도록 놓는 방법의 수를 구해야 합니다.

퀸은 같은 행, 같은 열, 대각선 방향으로 움직일 수 있기 때문에, 같은 행, 열, 대각선 방향에 두 개 이상의 퀸이 존재할 수 없습니다.

백트래킹 방식의 탐색을 수행하면됩니다.
각 행마다 가능한 열 위치를 탐색하고, 해당 열에 퀸을 놓았을 때, 이전 행들에 놓인 퀸들과 충돌하지 않으면 다음 행으로 이동합니다.
만약 조건을 만족하지 못하면 되돌아가서 다른 열을 시도합니다.

풀이

#include <vector>
#include <cmath>

using namespace std;


// 퀸을 올바르게 배치한 경우의 수를 저장하는 전역 변수
int answer;

// 현재 row 번째에 퀸을 놓는 것이 유효한지 검사하는 함수
bool isValid(vector<int>& col, int row)
{
    // 0행부터 현재 행 이전까지 검사
    for (int i = 0; i < row; ++i)
    {
        // 같은 열에 있거나, 대각선(왼쪽, 오른쪽)에 있는 경우 false 반환
        if (col[i] == col[row] || abs(col[i] - col[row]) == abs(i - row))
        {
            return false;
        }
    }
    
    return true;
}

// DFS와 백트래킹으로 가능한 퀸 배치 탐색
void dfs(int N, vector<int>& col, int row)
{
    // row가 N과 같아졌다는 것은 모든 행에 퀸을 유효하게 배치한 경우
    if (N == row)
    {
        ++answer;
        return;
    }
    
    // 현재 row 번째 행에서 N개의 열에 하나씩 퀸을 배치 시도
    for (int i = 0; i < N; ++i)
    {
        // row행 i열에 퀸을 배치
        col[row] = i;

        // 지금까지의 배치가 유효한 경우
        if (isValid(col, row))
        {
            // 다음 행 탐색으로 넘어간다.
            dfs(N, col, row + 1);
        }
    }
}

int solution(int n) {
    answer = 0;
    
    // 각 행의 퀸이 놓인 열 위치를 저장하는 배열
    vector<int> col(n);
    
    dfs(n, col, 0);
    
    return answer;
}

abs(col[i] - col[row]) == abs(i - row)가 대각선을 확인하는 것은 행 간 차이와 열 간 차이가 같다면 대각선 위에 있음을 의미하기 때문입니다.
수학식으로 $|x_1 - x_2| = |y_1 - y_2|$입니다.

예를 들어, (0, 1), (1, 2)를 확인한다면, col[0] = 1, col[1] = 2가 됩니다.
이것을 위의 식으로 계산해보면 $|0 - 1| = |1 - 2|$ 1로 값이 같으므로 같은 대각선이라는 의미가 됩니다.

성능 요약

시간 복잡도는 $O(N!)$입니다.

• 퀸 배치를 탐색하는 DFS함수 $O(N!)$
  • 각 단계마다 유효한 열만 다음 단계로 이어지기 때문
  • 첫 행에 N, 둘째 행 N - 1, 셋째 행 N - 2

공간 복잡도는 $O(n)$입니다.

• 각 행의 퀸이 놓인 열 위치를 저장하는 배열 vector<int> col $O(n)$
• 재귀 호출의 스택 $O(n)$
• $O(n) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.22MB)
테스트 3 〉 통과 (0.01ms, 4.17MB)
테스트 4 〉 통과 (0.01ms, 3.68MB)
테스트 5 〉 통과 (0.02ms, 4.21MB)
테스트 6 〉 통과 (0.05ms, 3.66MB)
테스트 7 〉 통과 (0.20ms, 4.21MB)
테스트 8 〉 통과 (0.88ms, 3.68MB)
테스트 9 〉 통과 (4.09ms, 4.2MB)
테스트 10 〉 통과 (20.85ms, 4.21MB)
테스트 11 〉 통과 (114.30ms, 4.15MB)