백트래킹 (Backtracking)_N-Queen

백트래킹(Backtracking)은 해를 찾기 위해 탐색 공간을 체계적으로 탐험하는 알고리즘 기법이다. 문제를 해결할 때 가능한 모든 경우의 수를 고려하지만, 불필요한 탐색을 줄이기 위해 잘못된 경로를 빨리 차단하고 다시 이전 상태로 돌아가는(백트래킹하는) 방식으로 동작한다.

백트래킹은 주로 재귀적인 방식으로 구현되며, 해를 찾기 위해 완전 탐색을 수행하되, 탐색 중 조건을 만족하지 않는 경로는 더 이상 탐색하지 않고 빠르게 포기하여 효율성을 높인다.

 

백트래킹의 핵심 개념

1. 후보해 생성(Partial Solution):
   • 문제를 해결하는 과정에서, 해결 가능한 해의 일부를 먼저 만들어 본다. 이때, 해가 아직 완성되지 않았을 수 있다.
2. 유망성 검사(Pruning):
   • 현재까지 만든 해가 유효한지(해를 구할 가능성이 있는지)를 검사한다. 만약 유효하지 않다면, 그 경로는 더 이상 탐색하지 않고 백트래킹(즉, 이전 상태로 돌아감)한다.
3. 해를 찾았는지 확인:
   • 해가 완성되면 이를 기록하거나 반환한다. 해가 완성되지 않았으면 계속해서 다음 가능한 경로를 탐색한다.

백트래킹은 문제를 부분적으로 해결하면서 나아가다가 더 이상 해답이 없다고 판단되면 뒤로 돌아가(백트랙) 다시 다른 경로를 시도하는 방식이다.

 

백트래킹의 일반적인 동작 구조

1. 현재 상태에서 가능한 후보지를 선택한다.
2. 후보지를 선택한 후, 해당 경로가 유효한지 확인한다.
3. 유망하지 않으면 백트래킹한다. 즉, 해당 경로에서 더 이상 탐색하지 않고 돌아간다.
4. 유망하면 재귀적으로 다음 단계로 진행하여 탐색을 계속한다.
5. 모든 가능한 경로를 탐색하거나, 원하는 해답을 찾으면 탐색을 종료한다.

 

백트래킹을 사용하는 대표적인 문제

백트래킹은 특히 조합적 최적화 문제와 결정 문제에서 많이 사용된다. 아래는 백트래킹을 적용하는 대표적인 문제들이다:

1. N-Queen 문제: N x N 체스판에서 N개의 퀸이 서로 공격하지 않도록 배치하는 방법을 찾는 문제.
2. 미로 탐색 문제: 미로에서 출구를 찾는 문제.
3. 수도쿠(Sudoku): 9x9 퍼즐에서 규칙에 맞게 숫자를 배치하는 문제.
4. 부분집합의 합 문제: 주어진 집합에서, 원소의 합이 특정 값이 되는 부분집합을 찾는 문제.
5. 최적화 문제: 예를 들어, 최대 이익을 내는 방법을 찾는 문제.

 

백트래킹의 장단점

장점:

1. 효율성: 백트래킹은 모든 가능한 경우의 수를 탐색하되, 불필요한 경로를 미리 차단함으로써 탐색 공간을 줄인다. 따라서 완전 탐색보다 훨씬 효율적이다.
2. 재귀적 구조: 재귀를 사용하여 매우 직관적이고 간결하게 문제를 해결할 수 있다.

단점:

1. 탐색 공간이 크면 비효율적일 수 있음: 백트래킹은 여전히 모든 경로를 탐색하는 알고리즘이므로, 탐색 공간이 매우 큰 경우에는 성능이 저하될 수 있다.
2. 구현 난이도: 문제에 따라 효율적인 가지치기(Pruning) 조건을 찾는 것이 어려울 수 있다. 잘못된 가지치기는 불필요한 탐색을 유발할 수 있다.

 

• 백트래킹은 문제를 부분적으로 해결해 나가며, 불필요한 경로를 효율적으로 가지치기하여 해결하는 알고리즘이다.
• 백트래킹은 완전 탐색과는 달리 가능성이 없는 경로는 조기에 포기하여 시간을 절약한다.
• N-Queen, 미로 찾기, 부분집합 문제, 퍼즐 문제 등에서 자주 사용된다.
• 탐색 공간이 너무 클 경우 성능 저하의 우려가 있으며, 효율적인 가지치기 조건을 찾는 것이 핵심이다.

 

N-Queen 문제란?

N-Queen 문제는 N x N 크기의 체스판 위에 N개의 퀸(Queen)을 배치하는 문제로, 각 퀸이 서로를 공격하지 않도록 배치해야 한다. 체스에서 퀸은 가로, 세로, 대각선 방향으로 원하는 만큼 이동할 수 있기 때문에, 한 퀸이 다른 퀸의 경로에 있으면 안된다.

이 문제의 목표는 N개의 퀸을 체스판에 모두 배치하는 방법을 찾는 것이다.

문제의 조건

• 퀸은 체스에서 가로, 세로, 대각선으로 이동할 수 있다.
• 따라서, 서로 다른 두 퀸이 같은 행, 열, 대각선에 있으면 안 된다.

예시 (4-Queen 문제):

• 4 x 4 체스판에 4개의 퀸을 배치하는 경우:

Q . . .    . Q . .    . . Q .    . . . Q
. . Q .    . . . Q    Q . . .    . Q . .
. Q . .    Q . . .    . . . Q    . . Q .
. . . Q    . . Q .    . Q . .    Q . . .

이 4가지 배치에서는 모든 퀸이 서로를 공격하지 않는다.

N-Queen 문제를 해결하는 방법

이 문제를 해결하려면 각 행에 하나의 퀸을 배치하고, 그 퀸이 다른 퀸과 공격 범위에 있지 않은지 확인하면서 배치를 진행한다. 일반적으로 이 문제는 백트래킹(Backtracking) 알고리즘을 사용하여 해결한다.

백트래킹 알고리즘의 주요 아이디어:

1. 첫 번째 행부터 차례대로 각 열에 퀸을 배치한다.
2. 퀸을 배치할 때마다 그 위치가 안전한지를 확인한다. 즉, 퀸이 이미 배치된 퀸들과 같은 열, 같은 대각선에 있지 않아야 한다.
3. 만약 퀸을 배치할 수 있으면 다음 행으로 이동하고, 그렇지 않으면 다른 열로 백트래킹하여 시도한다.
4. 모든 퀸을 배치하면 해결책이 하나 나오며, 모든 가능한 배치를 찾아야 한다면 탐색을 계속한다.

N-Queen 문제의 알고리즘 설계

1. 퀸 배치가 가능한지 확인하는 함수

퀸을 특정 위치에 놓을 수 있는지(안전한지)를 확인하는 함수가 필요하다. 이 함수는 세 가지 조건을 검사합니다:

• 같은 열에 퀸이 있는지 확인.
• 좌상단 대각선에 퀸이 있는지 확인.
• 우상단 대각선에 퀸이 있는지 확인.

2. 재귀적으로 퀸 배치

백트래킹 기법을 사용하여 각 행에 퀸을 하나씩 배치한다. 배치 가능한 열을 찾으면 다음 행으로 넘어가고, 불가능한 경우 이전 행으로 돌아와 다른 열을 시도한다.

N-Queen 문제 구현 (Python)

def is_safe(board, row, col, N):
    # 같은 열에 다른 퀸이 있는지 확인
    for i in range(row):
        if board[i][col] == 1:
            return False

    # 왼쪽 상단 대각선에 다른 퀸이 있는지 확인
    for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
        if board[i][j] == 1:
            return False

    # 오른쪽 상단 대각선에 다른 퀸이 있는지 확인
    for i, j in zip(range(row - 1, -1, -1), range(col + 1, N)):
        if board[i][j] == 1:
            return False

    return True

def solve_n_queens(board, row, N):
    # 모든 퀸을 배치했다면 해결책을 찾은 것
    if row == N:
        for r in board:
            print(r)
        print("\\n")
        return

    # 각 행에서 모든 열에 퀸을 놓아보기
    for col in range(N):
        if is_safe(board, row, col, N):
            board[row][col] = 1  # 퀸을 배치
            solve_n_queens(board, row + 1, N)  # 다음 행으로 이동
            board[row][col] = 0  # 백트래킹 (이 열에 퀸을 놓는 방법을 포기)

# N-Queen 문제 해결 (4-Queen 예시)
N = 4
board = [[0] * N for _ in range(N)]
solve_n_queens(board, 0, N)

코드 설명:

1. is_safe(board, row, col, N):
   • 현재 위치에 퀸을 놓을 수 있는지 확인하는 함수이다. 세 가지 조건을 확인한다.
   • 같은 열에 다른 퀸이 있는지.
   • 좌상단 대각선에 다른 퀸이 있는지.
   • 우상단 대각선에 다른 퀸이 있는지.
2. solve_n_queens(board, row, N):
   • 백트래킹 알고리즘의 핵심 함수이다. 각 행에 퀸을 배치하고, 그 다음 행으로 이동하면서 가능한 배치를 찾아 나간다.
   • 만약 퀸을 안전하게 배치할 수 없으면, 백트래킹을 통해 이전 상태로 돌아와 다른 열을 시도한다.
   • 모든 퀸을 성공적으로 배치했을 경우, 배치를 출력한다.

N-Queen 문제 해결 과정

4-Queen 문제를 예시로 들면, 다음과 같은 절차로 퀸을 배치한다:

1. 첫 번째 행에 첫 번째 퀸을 가능한 열에 놓는다.
2. 두 번째 행에서, 첫 번째 퀸과 같은 열, 대각선에 있지 않은 곳에 두 번째 퀸을 배치한다.
3. 세 번째 행에서도 동일하게 배치하며, 배치할 수 없으면 이전 행으로 돌아가(백트래킹) 다른 열에 퀸을 놓는다.
4. 이런 과정을 반복하여 모든 퀸을 배치할 수 있으면, 하나의 해를 출력한다.

4-Queen의 해결책 예시는 다음과 같다:

[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 1, 0, 0]

[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 1, 0]

N-Queen 문제의 시간 복잡도

N-Queen 문제는 기본적으로 모든 경우의 수를 탐색하기 때문에 완전 탐색에 가깝다. 따라서 이 문제의 시간 복잡도는 N! (팩토리얼)이다. 그러나 백트래킹을 통해 많은 경우의 수를 가지치기(Pruning)하여 탐색 공간을 줄일 수 있다.

1. 탐색할 수 있는 열의 수: 각 행마다 하나의 퀸을 배치하기 때문에, 첫 번째 행에서는 N개의 열을 탐색해야 한다.
2. 백트래킹으로 가지치기: 퀸을 배치할 때 안전하지 않은 경로는 빨리 포기할 수 있어 실제 탐색할 경우의 수는 N!보다 적다.

N-Queen 문제의 한계

1. 탐색 공간이 커질수록(즉, N이 클수록) 탐색 시간도 기하급수적으로 증가한다. N=8 이상의 경우, 백트래킹 없이는 효율적인 탐색이 어려워진다.
2. 백트래킹을 통한 최적화가 필수적이다. 가능하지 않은 경로를 빨리 배제함으로써 탐색 효율을 높인다.

N-Queen 문제의 확장

1. 다차원 N-Queen 문제: 2차원이 아닌 3차원 공간에서 퀸을 배치하는 문제로 확장할 수 있다. 3차원 체스판에서 퀸을 배치하는 문제를 해결하는 방식은 유사하지만, 대각선 탐색과 같은 부분이 더 복잡해진다.
2. 최적화: N이 클수록 시간이 많이 소요되기 때문에 다양한 최적화 기법(메모이제이션, 휴리스틱 탐색 등)을 도입할 수 있다.

 

• N-Queen 문제는 체스판에 퀸을 배치하는 문제로, 퀸들이 서로 공격하지 않도록 배치하는 방법을 찾는 문제이다.
• 백트래킹(Backtracking) 알고리즘을 사용하여, 각 행에 퀸을 배치하면서 불가능한 경로를 빨리 배제하고 새로운 경로를 탐색하는 방식으로 해결할 수 있다.
• 백트래킹을 통해 모든 경우를 탐색하지 않고, 가능한 배치를 효율적으로 찾을 수 있다.
• 이 문제는 조합적 최적화 문제의 대표적인 예로, 탐색 공간을 줄이기 위해 효율적인 가지치기(Pruning) 기법이 필수적이다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms