코딩 테스트 대비! 파이썬으로 N-Queen 문제 해결하기 (백트래킹 알고리즘)

파이썬으로 N-Queen 문제 해결하기 (백트래킹 알고리즘)


문제 설명

N-Queen 문제는 가로, 세로, 대각선으로 공격할 수 있는 퀸을 서로 공격하지 못하도록 N*N 크기의 체스판에 배치하는 문제입니다. N이 주어졌을 때, 퀸을 배치하는 방법의 수를 구하는 백트래킹 알고리즘을 작성하세요.


예시 입출력

입력: N = 4
출력: 2

입력: N = 8  
출력: 92

솔루션 코드

def n_queens(n):
    def is_safe(board, row, col, n):
        # 같은 행에 퀸이 있는지 검사
        for i in range(col):
            if board[row][i] == 1:
                return False

        # 왼쪽 대각선에 퀸이 있는지 검사
        i, j = row, col
        while i >= 0 and j >= 0:
            if board[i][j] == 1:
                return False
            i, j = i - 1, j - 1

        # 오른쪽 대각선에 퀸이 있는지 검사
        i, j = row, col
        while i >= 0 and j < n:
            if board[i][j] == 1:
                return False
            i, j = i - 1, j + 1

        return True

    def solve(board, col, n):
        if col == n:
            return 1

        count = 0
        for row in range(n):
            if is_safe(board, row, col, n):
                board[row][col] = 1
                count += solve(board, col + 1, n)
                board[row][col] = 0

        return count

    board = [[0 for j in range(n)] for i in range(n)]
    return solve(board, 0, n)

# 테스트 케이스
print("N=4 일 때 해의 개수:", n_queens(4))
print("N=8 일 때 해의 개수:", n_queens(8))

코드 설명

이 포스팅에서는 백트래킹 알고리즘을 활용하여 N-Queen 문제를 해결하는 방법을 다루었습니다. 백트래킹은 코딩 테스트에서 자주 출제되는 주제이며, 다양한 분야에 응용될 수 있어 반드시 학습해야 합니다.

백트래킹(Backtracking) 알고리즘은 해를 찾아가는 과정에서 잘못된 경로를 발견하면 되돌아가서 다른 경로를 탐색하는 방식입니다. N-Queen 문제에서는 각 열에 대해 가능한 모든 행을 체크하고, 퀸을 놓을 수 있는 경우 다음 열로 이동하여 재귀 호출을 합니다. 만약 더 이상 진행할 수 없는 경우 이전 단계로 되돌아가 다른 경로를 탐색합니다.

코드에서는 `is_safe` 함수를 사용하여 현재 위치에 퀸을 놓을 수 있는지 검사합니다. 가로, 세로, 대각선 방향으로 다른 퀸이 있는지 확인합니다. `solve` 함수에서는 백트래킹 알고리즘을 구현했습니다. 모든 열에 대해 각 행을 차례로 탐색하며, 안전한 위치에 퀸을 놓고 다음 열로 재귀 호출합니다. 마지막 열까지 도달하면 해를 찾은 것이므로 count를 증가시킵니다.

백트래킹 알고리즘은 조합 탐색, 제약 조건 만족 문제 등 다양한 분야에서 사용됩니다. 문제를 잘게 나누어 부분 문제를 해결하고, 이를 합쳐서 최종 해결책을 도출하는 방식입니다. 이러한 접근 방식을 익히면 복잡한 문제를 효과적으로 해결할 수 있습니다.