백트래킹 기법 N-Queen 문제 해결하기

백트래킹은 문제를 해결하는 데 있어 매우 강력한 기법으로, 다양한 최적화 문제와 탐색 문제에 사용됩니다. 이번 포스팅에서는 백트래킹 기법의 대표적인 예제 중 하나인 N-Queen 문제에 대해 설명하고, Java와 C로 구현해보겠습니다. 이 글을 통해 백트래킹의 기본 원리와 N-Queen 문제를 이해하는 데 도움이 되길 바랍니다.

백트래킹이란?

백트래킹(Backtracking)은 모든 가능한 경우의 수를 탐색하면서 조건에 맞지 않는 경로는 더 이상 진행하지 않고 돌아가는 방식의 알고리즘 기법입니다. 즉, 해가 될 가능성이 없는 경로는 미리 차단하여 탐색의 효율성을 높입니다. 이런 특성 때문에 백트래킹은 최적화 문제와 제약 충족 문제를 해결하는 데 자주 사용됩니다.

백트래킹의 기본 흐름

1. 결정 트리 탐색: 모든 가능한 후보를 트리 형태로 탐색합니다.
2. 가지치기: 특정 후보가 유망하지 않다고 판단되면 해당 후보를 배제하고 다음 후보로 넘어갑니다.
3. 해 탐색 종료: 해를 찾거나 모든 후보를 탐색할 때까지 반복합니다.

백트래킹은 DFS(깊이 우선 탐색)와 비슷하지만, 차이점은 가지치기를 통해 불필요한 탐색을 줄일 수 있다는 점입니다.

N-Queen 문제란?

N-Queen 문제는 N x N 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제입니다. 퀸은 같은 행, 열, 그리고 대각선 상에 있는 다른 퀸을 공격할 수 있기 때문에, 모든 퀸이 서로 공격하지 않도록 배치하는 것이 핵심입니다. 이 문제는 백트래킹을 활용하여 효율적으로 해결할 수 있습니다.

N-Queen 문제 해결 전략

1. 퀸을 한 행씩 놓아가며 유망한 위치를 탐색합니다.
2. 퀸이 서로 공격하지 않는 경우에만 다음 행으로 진행합니다.
3. 모든 행에 퀸을 놓으면 해를 찾은 것입니다.
4. 모든 가능한 경우를 시도하면서 해를 찾습니다.

Java로 구현한 N-Queen 문제

아래는 Java를 사용하여 N-Queen 문제를 백트래킹으로 해결하는 코드입니다.

public class NQueen {
    private int n;
    private int[] board;

    public NQueen(int n) {
        this.n = n;
        this.board = new int[n];
    }

    public void solve() {
        placeQueen(0);
    }

    private void placeQueen(int row) {
        if (row == n) {
            printBoard();
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row] = col;
                placeQueen(row + 1);
            }
        }
    }

    private boolean isSafe(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i] == col || Math.abs(board[i] - col) == Math.abs(i - row)) {
                return false;
            }
        }
        return true;
    }

    private void printBoard() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 8;  // 8-Queen 문제
        NQueen queen = new NQueen(n);
        queen.solve();
    }
}

Java 코드 설명

• placeQueen(int row): 현재 행에 퀸을 놓고, 유효하면 다음 행으로 진행합니다.
• isSafe(int row, int col): 현재 위치에 퀸을 놓아도 되는지 검사합니다. 같은 열이나 대각선에 다른 퀸이 있는지 확인합니다.
• printBoard(): 퀸의 배치 상태를 출력합니다.

C로 구현한 N-Queen 문제

다음은 C 언어를 사용하여 N-Queen 문제를 해결하는 코드입니다.

#include <stdio.h>
#include <stdlib.h>
#define N 8  // 8-Queen 문제

int board[N];

void printBoard() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i] == j) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

int isSafe(int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i] == col || abs(board[i] - col) == abs(i - row)) {
            return 0;
        }
    }
    return 1;
}

void placeQueen(int row) {
    if (row == N) {
        printBoard();
        return;
    }
    for (int col = 0; col < N; col++) {
        if (isSafe(row, col)) {
            board[row] = col;
            placeQueen(row + 1);
        }
    }
}

int main() {
    placeQueen(0);
    return 0;
}

C 코드 설명

• printBoard(): 체스판에 배치된 퀸의 상태를 출력합니다.
• isSafe(int row, int col): 현재 위치에 퀸을 놓을 수 있는지 검사합니다. 이전 행에서 같은 열이나 대각선에 퀸이 있는지 확인합니다.
• placeQueen(int row): 재귀적으로 퀸을 배치하여 모든 가능한 해를 찾습니다.

백트래킹의 장점과 단점

장점

• 효율적인 탐색: 불필요한 경로를 가지치기하여 탐색 시간을 줄일 수 있습니다.
• 직관적인 문제 해결: 재귀 호출과 조건 체크를 통해 문제를 쉽게 해결할 수 있습니다.

단점

• 복잡한 문제에서는 비효율적: N이 커질수록 경우의 수가 기하급수적으로 증가하여 시간 복잡도가 높아질 수 있습니다.
• 스택 오버플로우: 재귀 호출을 많이 사용하는 만큼, 큰 문제에서는 스택 오버플로우의 위험이 있습니다.

마무리

이번 포스팅에서는 백트래킹 기법을 활용하여 N-Queen 문제를 해결하는 방법을 알아보았습니다. 백트래킹은 가지치기를 통해 문제를 효율적으로 해결할 수 있는 강력한 도구입니다. Java와 C로 작성된 예제를 통해 백트래킹의 원리를 이해하고, 실제로 문제를 해결하는 데 도움이 되었기를 바랍니다.

N-Queen 문제는 다양한 크기의 체스판에 대해 퀸을 배치하는 문제로, 백트래킹 기법을 실습하기에 좋은 예제입니다. 이를 통해 백트래킹의 기본 개념과 활용법을 익히고, 더 복잡한 문제에 적용해보세요.