🚀 문제 요약

NxN 체스판에 N개의 퀸을 서로 잡을 수 없는 위치에 배치할 수 있는 경우의 수를 구하면 되는 문제

1️⃣ 접근법 1 (시간 초과)

• 퀸이 다른 말을 잡을 수 있는 경우를 체크한다.
  • 세로 같은 행에 있는 경우
  • 가로 같은 열에 있는 경우
  • 대각선 같은 열에 있는 경우
• NxN 체스판을 순회하며 퀸을 놓는 경우와 놓지 않는 경우로 재귀한다.
• 이때 재귀를 진행하다 해당 위치에 퀸을 놓는 경우 위의 사항에 해당 된다면 해당 분기는 잘라내기(백트래킹)
• 체스판 순회가 끝날 때까지 퀸을 N개 놓으면 경우의 수 추가

NxN 매트릭스를 재귀하는 방법으로 구현하면 계속해서 시간 초과가 발생하게 된다.

2️⃣ 접근법 2

힌트를 참고했다.

• Hint : 어차피 NxN 체스판에서 한 row에 한 퀸 밖에 둘 수 없다.
  • 이러면 NxN Matrix를 구성 안하고, 길이 N의 리스트에 각 요소는 퀸이 위치한 column의 값을 가지게 두면 된다.
  • 예를 들어 2x2 체스판이라고 가정 하고, (0, 0), (1, 1)에 퀸을 배치하면 [0, 1] 요런식
  • 가로 제약조건은 자동 만족하게 되며, 세로 제약조건은 값이 같은지만 검사하면 된다.
  • 두 점이 대각선 상에 위치하는지 확인하기 위해서는 두 점의 row의 차이와 col의 차이가 같은지를 검사하면 되므로 |현재 인덱스 - 비교 인덱스| == |현재 인덱스의 값 - 비교 인덱스의 값| 을 검사하면 된다.
    • 예를 들어 (0, 0), (1, 1)에 배치하여 [0, 1]인 경우
      • |현재 인덱스 - 비교 인덱스| = |0 - 1| = 1
      • |현재 인덱스의 값 - 비교 인덱스의 값| = |0 - 1| = 1
      • 같으므로 대각선에 위치하는 것
• pypy로 제출시 통과하며, python3로 제출 시 시간초과가 발생한다. (python3 통과하는 다른 스터디원들의 코드는 여기)

🔠 풀이 코드

import sys

input = sys.stdin.readline

def check_condition(row_idx: int) -> bool:
    '''
    퀸이 같은 열에 있는지 or 대각선 상에 배치되었는지 검사한다.
    '''
    for comp_idx in range(row_idx):     # 현재 row_idx 행까지 퀸이 배치되어 있음
        # 비교 과정 20행 부터 참고
        if matrix[row_idx]==matrix[comp_idx] or abs(row_idx-comp_idx)==abs(matrix[row_idx]-matrix[comp_idx]):
            return False

    return True

def recur(row_idx: int) -> None:
    '''
    재귀에 활용할 함수, 인자로 받은 row_idx 행에 col 값을 넣어보며 조건 검사에 만족하는 경우 퀸을 배치한다.
    '''
    global result

    if row_idx == N:            # N-1행까지 퀸이 배치 완료된 경우
        result += 1                 # 카운트 후 함수 종료
        return

    for col in range(N):                # row_idx행의 모든 컬럼에 퀸 배치해보기
        matrix[row_idx] = col           # 일단 배치 후

        if check_condition(row_idx):    # 조건에 만족하면
            recur(row_idx+1)            # 퀸을 배치 후 다음 row_idx+1행 탐색


N = int(input())
result = 0
matrix = [-1 for _ in range(N)]         # 문제 특성상 이와 같은 체스판 구성 가능, 16행 부터 참고
recur(0)
print(result)   

🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!

✏️ Algorithm Study

본 문제의 다른 풀이 및 피드백, 전체 문제 풀이 순서는 위 알고리즘 스터디 Repository에서도 확인 가능합니다.