[PCCP] Lv2: N-Queen(12952) 해설

문제

- 문제 링크: N-Queen

 

해설

- 자료구조: 

- 시간복잡도: 

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

 

(C++)

solution 1)

- N: 퀸의 개수

- 각 행에 퀸을 놓는 방법의 경우의 수는 N!이고, 시간 복잡도는 O(N!)

#include <algorithm>
#include <vector>

using namespace std;

// 현재 행에 이미 다른 퀸이 있는지 확인
bool isSameRow(int placedRow, int currentRow) { return placedRow == currentRow; }

// 대각선에 다른 퀸이 있는지 확인
bool isDiagonalAttack(int placedCol, int placedRow, int currentCol, int currentRow) {
    return abs(placedCol - currentCol) == abs(placedRow - currentRow);
}

// 퀸을 안전하게 배치할 수 있는지 확인
bool isSafePosition(const vector<int> &queen, int col, int row) {
    for (int i = 0; i< col; ++i) {
        if (isSameRow(queen[i], row) || isDiagonalAttack(i, queen[i], col, row)) {
            return false;
        }
    }
    return true;
}

// 퀸을 배치하는 함수
long long placeQueens(vector<int> &queen, int col) {
    int n = queen.size();
    if (col == n) {
        return 1;
    }
    
    long long count = 0;
    for (int row = 0; row < n; ++row) {
        // 퀸을 놓을 수 있는 위치면 퀸을 배치
        if (isSafePosition(queen, col, row)) {
            queen[col] = row;
            count += placeQueens(queen, col + 1);
            queen[col] = -1;
        }
    }
    return count;    
}

long long solution(int n) {
    vector<int> queen(n, -1);
    
    return placeQueens(queen, 0); // 퀸을 놓을 수 있는 경우의 수를 반환
}

solution 2)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

 

(Java)

solution 1)

- N: 퀸의 개수

- 각 행에 퀸을 놓은 방법의 경우의 수는 N!

- 시간 복잡도: O(N!)

class Solution {
    private static int N;
    private static boolean[] width;
    private static boolean[] diagonal1;
    private static boolean[] diagonal2;
    
    // 퀸이 서로 공격할 수 없는 위치에 놓이는 경우의 수를 구하는 함수
    private static int getAns(int y) {
        int ans = 0;
        // 모든 행에 대해서 퀸의 위치가 결정되었을 경우
        if (y == N) {
            // 해결 가능한 경우의 수를 1 증가시킴
            ans++;
        }
        else {
            // 현재 행에서 퀸이 놓일 수 있는 모든 위치를 시도
            for (int i = 0; i < N; ++i) {
                // 해당 위치에 이미 퀸이 있는 경우, 대각선상에 퀸이 있는 경우 스킵
                if (width[i] || diagonal1[i + y] || diagonal2[i - y + N])
                    continue;
                
                // 해당 위치에 퀸을 놓음
                width[i] = diagonal1[i + y] = diagonal2[i - y + N] = true;
                
                // 다음 행으로 이동하여 재귀적으로 해결 가능한 경우의 수 찾기
                ans += getAns(y + 1);
                // 해당 위치에 놓인 퀸을 제거
                width[i] = diagonal1[i + y] = diagonal2[i - y + N] = false;
            }
        }
        return ans;
    }
    
    public int solution(int n) {
        N = n;
        width = new boolean[n];
        diagonal1 = new boolean[n * 2];
        diagonal2 = new boolean[n * 2];
        int answer = getAns(0);
        return answer;
    }
}

solution 2)

#include<>

 

(Python)

solution 1)

- N: 퀸의 개수

- 각 행에 퀸을 놓는 방법의 경우: O(N!)

# 퀸이 서로 공격할 수 없는 위치에 놓이는 경우의 수를 구하는 함수
def getAns(n, y, width, diagonal1, diagonal2):
    ans = 0
    # 모든 행에 대해서 퀸의 위치가 결정되었을 경우
    if y == n:
        # 해결 가능한 경우의 수를 1 증가
        ans += 1
    else:
        # 현재 행에서 퀸이 놓일 수 있는 모든 위치를 시도
        for i in range(n):
            # 해당 위치에 이미 퀸이 있는 경우, 대각선상에 퀸이 있는 경우 스킵
            if width[i] or diagonal1[i + y] or diagonal2[i - y + n]:
                continue
            # 해당 위치에 퀸을 놓음
            width[i] = diagonal1[i + y] = diagonal2[i - y + n] = True
            # 다음 행으로 이동하여 재귀적으로 해결 가능한 경우의 수 찾기
            ans += getAns(n, y + 1, width, diagonal1, diagonal2)
            # 해당 위치에 놓인 퀸을 제거함
            width[i] = diagonal1[i + y] = diagonal2[i - y + n] = False
    return ans
    
def solution(n):
    # getAns 함수 호출하여 해결 가능한 경우의 수 찾기
    ans = getAns(n, 0, [False] * n, [False] * (n * 2), [False] * (n * 2))
    return ans

solution 2)

import

 

(JavaScript)

solution 1)

- N: 퀸의 개수

- 각 행에 퀸을 놓는 방법의 수: O(N!)

// 퀸이 서로 공격할 수 없는 위치에 놓이는 경우의 수를 구하는 함수
function search(n, y, width, diagonal1, diagonal2) {
    let answer = 0;
    // 모든 행에 대해서 퀸의 위치가 결정되었을 경우
    if (y === n) {
        // 해결 가능한 경우의 수를 1 증가시킴
        answer += 1;
    } else {
        // 현재 행에서 퀸이 놓일 수 있는 모든 위치를 시도
        for (let i = 0; i < n; ++i) {
            // 해당 위치에 이미 퀸이 있는 경우, 대각선 상에 퀸이 있는 경우 스킵
            if (width[i] || diagonal1[i + y] || diagonal2[i - y + n]) {
                continue;
            }
            // 해당 위치에 퀸을 놓음
            width[i] = diagonal1[i + y] = diagonal2[i - y + n] = true;
            
            // 다음 행으로 이동하여 재귀적으로 해결 가능한 경우의 수 찾기
            answer += search(n, y + 1, width, diagonal1, diagonal2);
            
            // 해당 위치에 놓인 퀸을 제거함
            width[i] = diagonal1[i + y] = diagonal2[i - y + n] = false;
        }
    }
    return answer;
}


function solution(n) {
    // search 함수 호출하여 해결 가능한 경우의 수 찾기
    const answer = search(n, 0, Array(n).fill(false), Array(n*2).fill(false), Array(n*2).fill(false));
    
    return answer;
}

solution 2)

import