Algorithm

[크래프톤 정글] 백준 9663번 N_queen 문제

하루이2222 2024. 9. 17. 17:03

N-Queens 문제 개요

N-Queens 문제는 N x N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제다. 퀸은 체스에서 가로, 세로, 대각선으로 공격할 수 있기 때문에, 서로 공격하지 않도록 배치하는 것이 핵심이다. 가능한 모든 배치 방법을 찾고, 그 개수를 계산하는 것이 목표다.

백트래킹 알고리즘 개요

백트래킹은 가능한 모든 경우를 탐색하면서, 조건에 맞지 않는 경우를 미리 포기하고 돌아가서 다른 경로를 시도하는 탐색 방법이다. 이 방식은 불필요한 탐색을 줄여주기 때문에 효율적이다.

백트래킹을 사용한 N-Queens 문제 해결 방법

  1. 처음 행(row = 0)부터 시작:
    • 탐색은 첫 번째 행(row = 0)부터 시작하여, 가능한 모든 열(col)에 퀸을 배치하는 시도를 한다.
    • 예를 들어, (0, 0)에 퀸을 놓고, 그 상태에서 재귀적으로 다음 행(row = 1)으로 이동하여 가능한 열에 퀸을 놓아본다.
  2. 각 행에서 for 문을 사용하여 모든 열 탐색:
    • for 문은 각 행에서 퀸을 놓을 수 있는 모든 열을 순차적으로 시도하는 역할을 한다.
    • 예를 들어, row = 1에서는 (1, 0), (1, 1), (1, 2), (1, 3) 등의 위치에 퀸을 놓아보는 시도를 차례대로 한다.
    • 각 열에 대해 퀸을 놓을 수 있는지 유효성 검사를 한다:
      • 같은 열에 다른 퀸이 있는지?
      • 왼쪽 위 대각선 또는 오른쪽 위 대각선에 다른 퀸이 있는지?
  3. 유효한 위치에 퀸을 놓고 다음 행으로 이동:
    • 퀸을 놓을 수 있는 유효한 위치를 찾으면, 그 위치에 퀸을 놓고 재귀 호출을 통해 다음 행으로 이동한다.
    • 예를 들어, row = 1에서 (1, 2)가 유효하면, 퀸을 그 위치에 놓고, row = 2로 이동하여 같은 방식으로 가능한 열을 탐색한다.
  4. 마지막 행까지 도달했을 때 하나의 해를 찾음:
    • 마지막 행(row = n-1)까지 도달해서 퀸을 유효하게 놓을 수 있다면, 이는 하나의 유효한 해를 찾은 것이다.
    • 해를 찾았을 때 가능한 해의 수를 저장하는 변수(cnt)를 1 증가시킨다.
    • 재귀 호출을 종료하고 이전 단계로 돌아간다.
  5. 백트래킹 수행: 이전 단계로 돌아가 다른 가능성 탐색:
    • 재귀 호출이 종료되면 이전 호출로 돌아가서, 이전 행에서 중단된 for 문 위치에서 다음 열로 이동하여 새로운 시도를 시작한다.
    • 예를 들어, (1, 2)에서 성공적으로 시도를 마치고 return되면, 다시 row = 1로 돌아가 (1, 3)에 대한 시도를 계속한다.
    • 이런 방식으로, 가능한 모든 열에 대해 탐색을 반복한다.
  6. 모든 경우를 다 시도했을 때 탐색 종료:
    • 백트래킹을 통해 첫 번째 행(row = 0)부터 시작해 모든 열을 탐색하고, 가능한 모든 경우를 시도했을 때 탐색이 완료된다.
    • 그 결과로, 가능한 모든 해를 찾을 수 있다.

예시로 백트래킹 이해하기

n = 4일 때 백트래킹 과정

  1. row = 0에서 시작:
    • (0, 0)에 퀸을 놓는다.
    • row = 1로 이동하여 (1, 0)부터 시작해 모든 열을 시도한다.
  2. row = 1에서 탐색:
    • (1, 0), (1, 1)은 유효하지 않다.
    • (1, 2)에 퀸을 놓는 것이 유효하므로, 그 위치에 놓고 row = 2로 이동한다.
  3. row = 2에서 탐색:
    • 모든 열을 시도하면서 유효한 위치를 찾는다. 예를 들어, (2, 3)이 유효하다고 하면 그 위치에 퀸을 놓고 row = 3으로 이동한다.
  4. row = 3에서 탐색:
    • 마지막 행에서 유효한 위치에 퀸을 놓을 수 있으면 하나의 해를 찾은 것이다.
    • 해를 찾았으니, cnt를 증가시키고 백트래킹을 통해 이전 행으로 돌아가며 다른 열을 시도한다.
  5. 다른 경로 탐색:
    • row = 1로 돌아와서 (1, 3)에 퀸을 놓는 시도를 한다.
    • 이런 방식으로 가능한 모든 경로를 탐색하여 모든 해를 찾는다.

중요한점

  • for 문은 각 행에서 가능한 모든 열을 탐색하는 역할을 한다.
  • 백트래킹은 유효하지 않은 경로를 빨리 포기하고, 다른 경로를 탐색할 수 있도록 하는 전략이다.
  • 재귀 호출은 각 행에서 가능한 열을 탐색하면서, 유효한 해를 찾기 위한 깊이 우선 탐색을 수행한다.

전체 트리 탐색 구조

n = 4

  1. 1단계: row = 0
    • (0, 0)에 퀸을 놓음
      • 2단계: row = 1 탐색 시작
        • (1, 0) → 가지치기 (같은 열에 퀸이 있음)
        • (1, 1) → 가지치기 (대각선에 퀸이 있음)
        • (1, 2) → 유효 (탐색 계속)
          • 3단계: row = 2 탐색 시작
            • (2, 0) → 가지치기 (대각선에 퀸이 있음)
            • (2, 1) → 가지치기 (같은 열에 퀸이 있음)
            • (2, 3) → 유효 (탐색 계속)
              • 4단계: row = 3 탐색 시작
                • (3, 0) → 유효 (해 발견, 해 1)
                • (3, 1) → 가지치기 (대각선에 퀸이 있음)
                • (3, 2) → 가지치기 (같은 열에 퀸이 있음)
                • (3, 3) → 가지치기 (대각선에 퀸이 있음)
              • 백트래킹: row = 2로 돌아감
            • (2, 3)에서 모든 탐색이 끝났으므로, 다시 row = 1로 돌아감.
        • 백트래킹: row = 1로 돌아가 다음 열 탐색 시작
        • (1, 3) → 유효 (탐색 계속)
          • 3단계: row = 2 탐색 시작
            • (2, 0) → 유효 (탐색 계속)
              • 4단계: row = 3 탐색 시작
                • (3, 1) → 유효 (해 발견, 해 2)
                • (3, 2) → 가지치기 (대각선에 퀸이 있음)
                • (3, 3) → 가지치기 (같은 열에 퀸이 있음)
            • 백트래킹: row = 2로 돌아감
            • (2, 1) → 가지치기 (대각선에 퀸이 있음)
            • (2, 2) → 가지치기 (대각선에 퀸이 있음)
            • (2, 3) → 가지치기 (같은 열에 퀸이 있음)
          • 백트래킹: row = 1로 돌아감
      • 백트래킹: row = 0로 돌아가 다음 열 탐색 시작
    • 1단계: row = 0의 다른 가능성 탐색
      • (0, 1)에 퀸을 놓음
        • 2단계: row = 1 탐색 시작
          • (1, 0) → 유효 (탐색 계속)
            • 3단계: row = 2 탐색 시작
              • (2, 0) → 가지치기 (같은 열에 퀸이 있음)
              • (2, 1) → 가지치기 (대각선에 퀸이 있음)
              • (2, 2) → 가지치기 (대각선에 퀸이 있음)
              • (2, 3) → 유효 (탐색 계속)
                • 4단계: row = 3 탐색 시작
                  • (3, 0) → 가지치기 (대각선에 퀸이 있음)
                  • (3, 1) → 가지치기 (같은 열에 퀸이 있음)
                  • (3, 2) → 가지치기 (대각선에 퀸이 있음)
                  • (3, 3) → 가지치기 (대각선에 퀸이 있음)
                • 백트래킹: row = 2로 돌아감
            • 백트래킹: row = 1로 돌아감
          • (1, 1) → 가지치기 (같은 열에 퀸이 있음)
          • (1, 2) → 가지치기 (대각선에 퀸이 있음)
          • (1, 3) → 가지치기 (대각선에 퀸이 있음)
        • 백트래킹: row = 0로 돌아가 다음 열 탐색 시작
      • (0, 2)에 퀸을 놓음
        • 같은 방식으로 진행
      • (0, 3)에 퀸을 놓음
        • 같은 방식으로 진행

전체 탐색 과정 요약

  • 탐색의 시작:
    • (0, 0)부터 시작하여 가능한 모든 열에 대해 시도하고, 유효한 경우 다음 행으로 이동한다.
    • 백트래킹: 유효하지 않거나 모든 경우를 시도한 후, 이전 단계로 돌아가 다른 경로를 탐색한다.
  • 모든 경우 탐색:
    • 가능한 모든 경로를 시도하여 모든 해를 찾는다.

구현


cnt = 0  # 가능한 해의 수를 저장할 변수

def n_queen(row, col, board):
    global cnt

    # 현재 행에 퀸이 있는지 검사
    if 1 in board[row]:
        return

    # 현재 열에 퀸이 있는지 검사
    for i in range(len(board)):
        if board[i][col] == 1:
            return

    # 왼쪽 위 대각선 검사
    i, j = row, col
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return
        i -= 1
        j -= 1

    # 오른쪽 위 대각선 검사
    i, j = row, col
    while i >= 0 and j < len(board):
        if board[i][j] == 1:
            return
        i -= 1
        j += 1

    board[row][col] = 1


    if row == len(board) - 1:
        cnt += 1
        board[row][col] = 0 # 백트래킹 
        return

    # 다음 행  재귀 호출
    for next_col in range(len(board)):
        n_queen(row + 1, next_col, board)

    # 백트래킹
    board[row][col] = 0 


n = int(input())

board = [[0 for _ in range(n)] for _ in range(n)]

for col in range(n):
    n_queen(0, col, board)

print(cnt)