백준: N Queen(9663)

알고리즘 문제 해결 과정을 기록합니다

September 22, 2025 · 3 min read

문제 개요 #

Source: 백준 링크
Difficulty: Gold 4
Key Concept: 백트래킹

접근 방법 #

처음 문제를 풀었을 때는 퀸을 놓으려는 좌표를 기준으로 행, 열, 대각선 모두 체크하여 놓을 수 있는지 확인 후 다음 행의 퀸을 놓을 수 있도록 함수를 넘기도록 하였습니다. 즉 row별로 검증 후 퀸을 두고, 모든 row에 퀸이 놓아졌다면 result를 1 추가하도록 하였습니다.

시행착오 #

처음 대각선 검증 로직에서 아래와 같이 검사를 하였습니다.

for(int i = 0 ; i < n ; i++){
    if(row-i < 0 || row + i>= n || col - i < 0 || col +i>=n) {continue;}

    if(board[row-i][col-i] || board[row+i][col+i] ||
        board[row-i][col+i] || board[row+i][col-i]) {return false;}
}

해당 i는 row-i, row+1, col-i, col+i가 모두 갈 수 있는 끝 좌표, 즉 모두 0 또는 N-1까지 가도록 i값의 범위를 가져야 합니다. 따라서 while문을 이용하여 올바른 검증을 구현하였습니다.

해결 방법 #

int n, answer = 0;
int board[20][20];
const int dr[] = {1, -1, 1, -1};
const int dc[] = {-1, -1, 1, 1};

bool isValid(int row, int col) {
    // 열 또는 행에 이미 퀸이 있다면 return false
    for (int i = 0; i < n; i++) {
        if (board[i][col]) {
            return false;
        }
    }

    // 대각선 방향으로 검증
    int i = 1;
    while(row-i >= 0 && col - i >= 0){
        if(board[row-i][col-i]) {return false;}
        i++;
    }
    i = 1;
    while(row+i < n && col+i < n){
        if(board[row+i][col+i]) {return false;}
        i++;
    }
    i = 1;
    while(row - i >= 0 && col+i < n){
        if(board[row-i][col+i]) { return false;}
        i++;
    }
    i = 1;
    while(row+i < n && col - i >= 0){
        if(board[row+i][col-i]) {return false;}
        i++;
    }

    return true;
}

void dfs(int row) {  // 한 행 마다 퀸을 두어야 함
    if (row == n) {  // 모든 행에 퀸이 채워졌다면
        answer++;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!isValid(row, i)) {  // 해당 좌표에 퀸을 놓을 수 있는지 확인
            continue;
        }
        board[row][i] = 1;  // 퀸 두기
        dfs(row + 1);       // 다음 행
        board[row][i] = 0;  // 퀸 회수
    }
    return명
}

알고리즘 개선 및 설명 #

int n, used1[20],used2[40], used3[40],answer=0;

void backTracking(int cur_row){
    if(cur_row == n){
        answer++;
        return;
    }

    for(int cur_col = 0 ; cur_col < n ;cur_col ++){
        if(used1[cur_col] || used2[cur_col+cur_row] || used3[cur_row - cur_col + n - 1]){continue;}
        used1[cur_col] = 1;
        used2[cur_col+cur_row] = 1;
        used3[cur_row - cur_col + n - 1] = 1;
        backTracking(cur_row+1);
        used1[cur_col] = 0;
        used2[cur_col+cur_row] = 0;
        used3[cur_row - cur_col + n - 1] = 0;
    }
}

N-Queen 문제는 행을 위에서 아래로 내려가면서 3가지만 검증하면 되는 문제이다. 동일 열, 우상방향의 대각선, 우하방향의 대각선만 검증해서 퀸이 없다면 해당 자리에는 퀸을 놓을 수 있다. used1은 동일 열에 퀸이 있는지 확인하기 위한 배열이다. used2는 배열의 인덱스를 좌표계로 바꾼다면 열이 커질수록 행의 값이 작아지는 우상 방향의 대각선이다. 이를 수식으로 표현하면 $y=-x+c \Leftrightarrow y+x =c$이므로 우상 대각선의 좌표들은 모두 행과 열의 합이 동일한 값을 가지고 있음을 알 수 있다. used3도 동일하게 수식으로 표현하면 $y=x+c \Leftrightarrow y-x=c$이므로 우하 대각선의 좌표들은 모두 행에서 열을 뺀 값이 동일함을 알 수 있다. 인덱스는 음수가 될 수 없으므로 n-1을 더하여 음수가 아닌 수로 보정시켜 주면 된다.

따라서 used2는 해당 좌표의 cur_row + cur_col을 1로 처리하고 used3는 해당 좌표의 cur_row - cur_col + n - 1을 1로 처리하여 우하 대각선을 모두 방문 처리하여 주었다.

성능 분석 #

Time Complexity: $O(N!)$

핵심 정리 #

단순히 열과 모든 대각선을 비교할 수도 있지만, 좌표계의 개념을 떠올려 대각선의 좌표들은 모두 하나의 일차식 안에 있는 값들이고 이는 행과 열의 연산을 통하면 특정한 값들을 들고 있다는 사실을 도출해내어 더욱 효과적일 로직을 짤 수 있음을 알 수 있었습니다.

Pelikan's Glide