[Programmers]N-Queen

N-Queen

난이도: level 2

정답률: 38% (2024.07.31 기준)

완료한 사람: 6359명 (2024.07.31 기준)

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12 이하의 자연수입니다.

입출력 예시)

n	result
1	1
2	0
3	0
4	2

 

 

 

 

해당 문제는 백트래킹을 이용하여 문제를 풀어봤습니다.

 

고려할 점

• 2차원의 보드이지만 배열의 index를 행이라고 생각하면 1차원 배열로 표현이 가능하다.
• 2가지 기능을 구현해야 한다. 
  1st. 퀸을 배치하는 모든 경우의 수 구하기 -> 백트래킹
  2nd. 경우의 수 중에 조건을 만족하는 경우 찾는 부분 -> 2가지

 

1. board를 이용한 풀이

해당 풀이는 n이 짝수일 경우에 가운데를 기준으로 대칭이 되는 경우가 있으므로 고려해서 짜면 시간 복잡도를 줄일 수 있다.

def solution(n):
  """
  n x n 크기의 체스판에 퀸을 서로 공격할 수 없게 배치하는 경우의 수를 계산하는 함수

  Args:
    n: 체스판의 한 변의 길이

  Returns:
    퀸을 배치할 수 있는 경우의 수
  """

  def is_promising(board, row, col):
    """
    (row, col) 위치에 퀸을 놓았을 때, 다른 퀸과 충돌하는지 확인하는 함수

    Args:
      board: 현재까지 배치된 퀸의 위치를 저장하는 리스트
      row: 현재 행
      col: 현재 열

    Returns:
      충돌하지 않으면 True, 충돌하면 False
    """
    # 같은 열에 퀸이 있는지 확인
    for i in range(row):
      if board[i] == col or \
         board[i] - i == col - row or \
         board[i] + i == col + row:
        return False
    return True

  def backtrack(row):
    """
    백트래킹을 이용하여 퀸을 배치하는 함수

    Args:
      row: 현재 처리 중인 행의 인덱스
    """
    nonlocal answer  # 외부 변수 answer에 접근하기 위해 사용

    if row == n:  # 모든 행에 퀸을 배치했으면 경우의 수를 1 증가
      nonlocal answer
      answer += 1
      return

    for col in range(n):
      if is_promising(board, row, col):  # 현재 위치에 퀸을 놓을 수 있으면
        if n % 2 == 0 and row == 0 and col >= n // 2:  # 짝수일 때 대칭성을 이용한 가지치기
          continue
        board[row] = col  # 퀸을 배치
        backtrack(row + 1)  # 다음 행으로 이동
        board[row] = -1  # 백트래킹: 현재 위치의 퀸을 제거

  answer = 0
  board = [-1] * n  # board[i]는 i번째 행에 있는 퀸의 열 위치를 나타냄
  backtrack(0)
  return answer if n % 2 == 1 else answer * 2

 

2. 각각의 조건 가능 여부를 저장하여 풀이

보드의 경우보다는 조건을 확인 가능한 배열을 확인하여 문제를 풀기 때문에 시간 복잡도가 빠르다.

 

• col: 각 열에 퀸이 배치되었는지를 추적하는 불리언 배열입니다. col [i]는 i열에 퀸이 배치되었는지를 나타냅니다.
• cross1: 대각선 방향의 공격을 추적하는 불리언 배열입니다. cross1 [(y - x) + n]는 y - x대각선에 퀸이 배치되었는지를 나타냅니다.
• cross2: 또 다른 대각선 방향의 공격을 추적하는 불리언 배열입니다. cross2 [y + x]는 y + x대각선에 퀸이 배치되었는지를 나타냅니다.

 

def solution(n):
  """
  n x n 크기의 체스판에 퀸을 서로 공격할 수 없게 배치하는 경우의 수를 계산하는 함수입니다.

  Args:
    n: 체스판의 한 변의 길이

  Returns:
    퀸을 배치할 수 있는 경우의 수
  """

  answer = 0
  col = [False] * n  # 각 열에 퀸이 있는지 여부를 저장하는 리스트
  cross1 = [False] * (2*n)  # 대각선(왼쪽 위에서 오른쪽 아래)에 퀸이 있는지 여부를 저장하는 리스트
  cross2 = [False] * (2*n)  # 대각선(오른쪽 위에서 왼쪽 아래)에 퀸이 있는지 여부를 저장하는 리스트

  def back(y):
    """
    백트래킹 함수로, y번째 행에 퀸을 배치하는 경우를 재귀적으로 처리합니다.

    Args:
      y: 현재 처리 중인 행의 인덱스
    """
    nonlocal answer  # 외부의 answer 변수를 수정하기 위해 사용

    if y == n:  # 모든 행에 퀸을 배치했으면 경우의 수를 1 증가시킵니다.
      answer += 1
      return

    for x in range(n):  # 현재 행의 각 열에 대해
      if col[x] or cross1[n-(x-y)] or cross2[x+y]:  # 해당 위치에 퀸을 놓을 수 없으면 다음 열로 이동
        continue

      # 퀸을 배치할 수 있는 경우
      col[x] = True  # 해당 열에 퀸을 배치
      cross1[n-(x-y)] = True  # 대각선1에 퀸을 배치
      cross2[x+y] = True  # 대각선2에 퀸을 배치
      back(y+1)  # 다음 행으로 재귀 호출

      # 백트래킹: 현재 위치의 퀸을 제거
      col[x] = False
      cross1[n-(x-y)] = False
      cross2[x+y] = False

  back(0)  # 첫 번째 행부터 백트래킹 시작
  return answer

 

2개의 방식 모두 백트래킹을 이용한 방법이지만 어떻게 알고리즘을 짜느냐에 따라 시간 복잡도에서 큰 차이를 보여준다. 효율적인 부분을 고려하여 좋은 코딩을 하자!