[백트랙킹] 9663번 N-queen (미해결)

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 2시간 + a

1. 문제 설명

- https://www.acmicpc.net/problem/9663

9663번: N-Queen

2. 접근 방식

- 재귀적인 방식으로 코드를 구현해야 한다.

※ 해당 문제는 "파이썬"코드로 작성 시에 시간 초과가 된다. 특정한 조건들을 더 고려해야 할 필요가 있을 것 같다.

3. 코드

- Permutation 활용 (메모리 초과_실패)

# 메모리 초과

from itertools import permutations
def check_queen(ls):
    for i in range(n-1):
        x, y = ls[i]
        for a,b in ls[i+1:]:
            if abs(x-a) == abs(y-b):
                return 0
    return 1

n = int(input())
count = 0
for nn_xy in list(permutations(list(range(0, n)), n)): ## 행방향 같은 거 X, 열방향 같은 거)
    tmp=[]
    for x, y in enumerate(nn_xy):
        tmp.append((x, y))
    count += check_queen(tmp)
print(count)

- 백트랙킹 구현 (가장 효율적으로 보였던 코드)

def is_promising(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i): # 대각선 찾기
            return False
    return True

def n_queens(x):
    global ans
    if x == n:
        ans += 1
    else:
        for i in range(n):
            # [x, i]에 퀸을 놓는다.
            row[x] = i
            if is_promising(x):
                n_queens(x+1)

n = int(input())
ans = 0
row = [0] * n # 1차원으로 메모리 절약
n_queens(0)
print(ans)

4. 코멘트

- 처음에는 itertools 라이브러리를 활용해서 문제를 풀려고 노력해서 1시간 반 정도 걸려서 코드를 구현했는데 결국 실패 했다. 처음에는 combination을 했는데, 8x8만 해도 수가 너무 커져서 열 부분만 생각해서 permutation을 만들었다.  코드를 대폭 줄일 수 있었지만, '메모리 초과'가 나왔다.

- 결국 백트랙킹으로 구현을 하려고 했는데, '시간 초과'가 나서 다른 2021년 포스팅된 블로그에 정리된 코드들을 참고했다. 하지만 그럼에도 시간 초과가 나는 것을 확인했다. 현재 특정한 조건이 추가가 되어서인지 파이썬 코드로는 통과가 안되는 것 같다. 내일 조금 더 알아볼 필요가 있을 것 같다.

- 이래나 저래나 N-queens문제는 재귀를 이해하기 좋은 코드라고 생각한다. 해당 알고리즘을 이해할 수 있게 다시 복습할 필요가 있을 것 같다.