프로그래머스 | Level 2 | N-Queen

Programmers | Level 2 | N-Queen

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Backtracking

󰧭 Description

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

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

▢ ▦ ▢ ▢
▢ ▢ ▢ ▦
▦ ▢ ▢ ▢
▢ ▢ ▦ ▢

▢ ▢ ▦ ▢
▦ ▢ ▢ ▢
▢ ▢ ▢ ▦
▢ ▦ ▢ ▢

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

 Constraints

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

󰦕 Examples

n	result
4	2

Solutions

󰘦 Code

import java.util.*;

class Solution {
    public int solution(int n) {
        int[] queens = new int[n];  // 각 행에 배치된 퀸의 열 위치를 저장할 배열
        return place(queens, 0, n);  // 첫 번째 행부터 퀸을 배치하는 재귀 호출 시작
    }
    
    // 퀸을 배치하는 재귀 함수
    private int place(int[] queens, int row, int n) {
        if (row == n) return 1;  // 모든 퀸을 성공적으로 배치한 경우 1 반환
        
        int count = 0;  // 가능한 배치 수를 저장할 변수
        for (int col = 0; col < n; col++) {  // 현재 행에서 모든 열에 퀸을 배치 시도
            if (isSafe(queens, row, col)) {  // 퀸을 배치할 수 있는지 확인
                queens[row] = col;  // 퀸을 해당 열에 배치
                count += place(queens, row + 1, n);  // 다음 행으로 넘어가 재귀 호출
            }
        }
        return count;  // 가능한 배치 수 반환
    }
    
    // 현재 퀸을 해당 위치에 배치해도 안전한지 확인하는 함수
    private boolean isSafe(int[] queens, int row, int col) {
        // 현재 행 이전에 배치된 퀸들과 비교하여 충돌이 발생하는지 확인
        for (int i = 0; i < row; i++) {
            if (isUnderAttack(i, queens, row, col)) return false;  // 충돌 발생 시 false 반환
        }
        return true;  // 안전하면 true 반환
    }
    
    // 퀸이 서로 공격할 수 있는지 확인하는 함수
    private boolean isUnderAttack(int i, int[] queens, int row, int col) {
        if (queens[i] == col) return true;  // 같은 열에 있으면 충돌
        if (Math.abs(queens[i] - col) == Math.abs(i - row)) return true;  // 대각선 상에 있으면 충돌
        
        return false;  // 충돌이 없으면 false 반환
    }
}

 Approaches

이 문제는 백트래킹(Backtracking)을 활용한 탐색 문제로, 가능한 모든 경우의 수를 탐색하되, 중간에 잘못된 경로는 포기하고 더 나은 경로를 찾는 방식입니다. N개의 퀸을 서로 공격하지 않도록 배치하기 위해서는 행, 열, 대각선을 고려한 안전한 배치를 찾아야 합니다. 이러한 문제 유형은 보통 조합적 탐색 혹은 제약 충족 문제에 해당합니다.

1. 문제 분석

N-Queen 문제는 주어진 체스판 크기 n에서 n개의 퀸을 서로 공격할 수 없도록 배치하는 문제입니다. 퀸은 가로, 세로, 대각선 방향으로 이동하며 공격할 수 있기 때문에, 이 세 가지 공격 경로에 대한 충돌을 피하도록 퀸을 배치해야 합니다. 즉, 각 퀸은 다른 퀸과 동일한 열이나 행에 위치할 수 없고, 대각선 상에도 위치할 수 없습니다.

이 문제를 해결하기 위해서는 백트래킹(Backtracking) 기법을 사용하여 가능한 모든 퀸 배치 방법을 탐색하는 방법이 적합합니다. 백트래킹은 가능한 모든 배치를 시도하되, 중간에 충돌이 발생하면 그 시도를 포기하고 다른 경로를 탐색하는 방식으로 진행됩니다. 이를 통해 최종적으로 퀸을 배치할 수 있는 모든 가능한 방법을 찾아냅니다.

2. 접근 방식

N-Queen 문제를 해결하기 위해서는 백트래킹 알고리즘을 사용하여, 각 행에 퀸을 배치할 때 조건을 만족하는지 확인하고, 만족하지 않으면 해당 경로를 되돌아가 다른 경로를 시도하는 방식으로 풀이합니다. 기본적인 접근 방식은 다음과 같습니다:

1. 재귀 탐색: 첫 번째 행부터 시작해 각 행에 하나씩 퀸을 배치해 나갑니다. 만약 현재 행에 퀸을 배치할 수 있으면, 다음 행으로 넘어가서 그곳에 퀸을 배치하는 재귀적인 탐색을 수행합니다. 만약 현재 행에 퀸을 배치할 수 없다면, 그 이전의 행에서 배치를 변경해야 합니다.
2. 안전성 확인: 퀸을 배치할 때, 다른 퀸들과 가로, 세로, 대각선 방향으로 공격할 수 있는지 확인합니다. 이를 위해 현재까지 배치된 퀸의 위치를 저장하고, 새롭게 배치하려는 퀸이 기존 퀸들과 충돌하는지 체크합니다.
3. 백트래킹: 퀸을 배치할 때 충돌이 발생하면, 그 자리에는 퀸을 놓을 수 없으므로 다른 열을 탐색합니다. 이 과정을 재귀적으로 반복하면서 가능한 모든 배치를 탐색합니다.

3. 퀸의 배치 준비

백트래킹을 수행하기 위해, 먼저 퀸이 체스판에 배치될 수 있는 위치를 기록할 배열을 초기화합니다. 이 배열은 각 행에 배치된 퀸의 열 번호를 저장하는 역할을 합니다. 이 배열을 통해 각 행의 퀸이 어느 열에 위치하는지를 기록하며, 첫 번째 행부터 재귀적으로 탐색하여 퀸을 배치할 수 있는 모든 가능한 위치를 찾아나갑니다.

// 각 행에 배치된 퀸의 열을 기록할 배열
int[] queens = new int[n];

4. 백트래킹을 통한 퀸 배치

다음은 백트래킹을 통해 각 행에 퀸을 배치하면서 가능한 모든 배치를 탐색합니다. 기본적으로 첫 번째 행부터 시작해 한 행씩 퀸을 배치하며, 그다음 행으로 넘어가 계속해서 퀸을 배치합니다. 이 과정은 재귀적으로 이루어집니다.

각 재귀 호출은 현재 행에 퀸을 배치할 수 있는지 확인한 후, 해당 위치에 퀸을 놓고 다음 행으로 넘어가게 됩니다. 만약 현재 행에 퀸을 안전하게 배치할 수 없다면, 다른 열을 시도해보거나 이전 행으로 돌아가서 다른 위치에 퀸을 배치하는 시도를 합니다.

재귀 함수는 마지막 행까지 퀸을 배치하게 되면, 이는 유효한 배치임을 의미하며 1을 반환합니다. 이 1은 가능한 유효한 배치가 하나 있다는 것을 나타내며, 재귀적으로 반환되는 값들이 모두 더해져 최종적으로 가능한 배치 수를 계산하게 됩니다.

이 과정은 각 행의 모든 열에 대해 퀸을 배치하는 것을 시도하며, 모든 경우를 탐색합니다. 하지만 각 열에 퀸을 배치하기 전, 해당 위치에 퀸을 놓아도 안전한지를 확인하는 과정이 필요합니다. 이 안전성 체크는 별도의 함수로 분리하였습니다.

private int place(int[] queens, int row, int n) {
    if (row == n) return 1;  // 모든 퀸을 배치한 경우
    int count = 0;
    
    // 현재 행에서 가능한 모든 열에 퀸을 배치 시도
    for (int col = 0; col < n; col++) {
        if (isSafe(queens, row, col)) {  // 해당 위치가 안전한지 확인
            queens[row] = col;  // 퀸을 해당 열에 배치
            count += place(queens, row + 1, n);  // 다음 행 탐색
        }
    }
    
    return count;  // 가능한 배치 수 반환
}

5. 퀸이 안전하게 배치될 수 있는지 확인

퀸을 새로운 위치에 배치할 때는, 해당 위치가 이전에 배치된 다른 퀸들과의 충돌이 없는지 확인해야 합니다. 퀸은 가로, 세로, 대각선 방향으로 공격할 수 있으므로, 이 세 가지 경로에서 다른 퀸과 겹치지 않도록 배치해야 합니다. 이를 확인하는 과정에서 현재 행까지 배치된 퀸들과 비교하여 해당 위치가 안전한지 검증합니다.

이 검증 과정은 두 단계로 이루어집니다:

• 같은 열에 다른 퀸이 있는지 확인: 같은 열에 퀸이 있으면 그 위치는 안전하지 않으므로 해당 위치에 퀸을 배치할 수 없습니다.
• 대각선 상에 퀸이 있는지 확인: 대각선에서의 공격 여부는 두 퀸의 행 차이와 열 차이가 같은지에 따라 판단됩니다. 만약 이 두 차이가 동일하다면, 해당 위치도 안전하지 않으므로 퀸을 배치할 수 없습니다.

대각선의 기하학적 정의
대각선이란 두 점 사이의 수직 거리(행 차이)와 수평 거리(열 차이)가 동일한 경우를 말합니다. 좌표 평면에서 두 점이 대각선 상에 있다는 것은 두 점이 같은 각도로 기울어져 있음을 의미합니다.

private boolean isSafe(int[] queens, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (isUnderAttack(i, queens, row, col)) return false;  // 충돌 발생 시 false
    }
    return true;  // 안전한 경우 true 반환
}

private boolean isUnderAttack(int i, int[] queens, int row, int col) {
    if (queens[i] == col) return true;  // 같은 열에 있는 경우
    if (Math.abs(queens[i] - col) == Math.abs(i - row)) return true;  // 대각선에 있는 경우
    return false;  // 충돌이 없는 경우
}

6. 퀸 배치 가능 수 반환

이제 모든 행에 퀸을 배치할 수 있는 경우의 수를 계산하여 반환하는 단계입니다. 첫 번째 행부터 재귀적으로 탐색을 시작하여, 각 행에 퀸을 배치할 수 있는 위치를 찾아 나가면서 가능한 모든 경우를 합산합니다. 최종적으로 조건을 만족하는 퀸 배치 방법의 총 개수를 반환합니다.

// 가능한 퀸 배치 경우의 수를 계산하고 반환
return place(queens, 0, n);

󰄉 Complexity

• ⏳ TC: O(n!)
• 💾 SC: O(n)

N개의 퀸을 배치하는 경우의 수는 O(n!)입니다. 각 퀸을 서로 다른 행에 배치하며, 열과 대각선에 대한 조건을 검증하는 과정이 반복됩니다. 백트래킹을 통해 비효율적인 경로를 빠르게 배제하지만, 최악의 경우에도 모든 가능한 배치를 시도해야 하므로 시간 복잡도는 O(n!)입니다.

퀸의 배치 상태를 저장하는 배열의 크기는 n이므로, 공간 복잡도는 O(n)입니다. 이 배열은 각 행에서 퀸이 어느 열에 있는지를 기록합니다.