[프로그래머스]N-퀸

[50] N-퀸

책 구매하기

문제 정보

• 분류: 백트래킹
• 정답률: 36%
• 권장 시간 복잡도: O(N!)
• 핵심 키워드: N-Queen, 백트래킹, 열/대각선 체크, 재귀
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12952

문제를 읽을 때 체크할 포인트

한 행에 퀸을 하나씩 두고, 열과 두 대각선이 겹치지 않는 경우만 다음 행으로 내려가면 된다. 전형적인 백트래킹 문제다.

한 번의 선택으로 답이 확정되지 않고, 가능한 경우를 조건에 맞게 잘라 가며 끝까지 봐야 하는 유형이다. 그래서 '무엇을 상태로 들고 갈지'를 먼저 정하는 게 중요하다.

풀이 흐름

1. 행을 하나씩 내려가며 놓을 열을 고른다.
2. 열, 좌상우하 대각선, 우상좌하 대각선 사용 여부를 검사한다.
3. 마지막 행까지 도달한 경우의 수를 센다.

구현할 때 놓치기 쉬운 부분

열, 왼쪽 대각선, 오른쪽 대각선을 각각 막아야 한다. 한 방향만 검사하거나 대각선 인덱스를 잘못 계산하면 유효하지 않은 배치가 통과한다.

파이썬 정답 코드

def solution(n):
  # 행을 하나씩 내려가며 놓을 열을 고른다.
  used_col = [False] * n
  used_diag1 = [False] * (2 * n)
  used_diag2 = [False] * (2 * n)
  answer = 0

  def dfs(row):
    nonlocal answer
    if row == n:
      answer += 1
      return

    for col in range(n):
      d1 = row + col
      d2 = row - col + n
      if used_col[col] or used_diag1[d1] or used_diag2[d2]:
        continue
      used_col[col] = used_diag1[d1] = used_diag2[d2] = True
      dfs(row + 1)
      used_col[col] = used_diag1[d1] = used_diag2[d2] = False

  dfs(0)
  # 열, 좌상우하 대각선, 우상좌하 대각선 사용 여부를 검사한다.
  return answer

시간 복잡도

N은 체스판 한 변 길이이다.

가능한 순서나 배치를 끝까지 시도하는 완전탐색 구조이다. 원소 N개의 순열을 모두 보는 최악의 경우를 기준으로 하면 factorial 차수가 남는다.

따라서 시간 복잡도는 O(N!)이다.