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

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

소요시간: 2시간 + a

1. 문제 설명

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

9663번: N-Queen

2. 접근 방식

> 출처: https://rebas.kr/761 [PROJECT REBAS] 참고

- y축, 대각선 (/)방향, 역대각선 방향(\) 총 3가지의 경우를 True, False로 설정해서 재귀문을 돈다.

- 이렇게 함으로써 조건을 확인하기 위해 별도로 리스트를 생성하는 등의 불필요한 변수선언을 줄일 수 있음으로 메모리와 시간을 줄일 수 있다.  

3. 코드

- 통과 코드 (22/01/11) 기준

n, ans = int(input()), 0
# y축[n개], 대각선(/)[2n개],  역대각선(\)[2n개] 총 3방향을 확인
a, b, c = [False]*n, [False]*(2*n-1), [False]*(2*n-1)

def solve(i):
    global ans
    if i == n:
        ans += 1
        return
    
    for j in range(n):
        # 세 가지 조건이 모두 False여야만 함
        if not (a[j] or b[i+j] or c[i-j+n-1]):
            a[j] = b[i+j] = c[i-j+n-1] = True
            solve(i+1)
            a[j] = b[i+j] = c[i-j+n-1] = False
solve(0)
print(ans)

4. 코멘트

- 이전에 N-queens 문제를 풀면서 메모리 초과, 시간 초과 이슈가 있어서 이번엔 아예 각을 잡고 검색을 해서 통과가 가능한 코드를 확인할 수 있었다. 해당 코드의 경우 이전의 다른 블로거들이 사용했었던 조건을 확인하는 부분을 별도의 T/F 리스트를 사용함으로써 for문을 줄일 수 있었다. 

- 해당 코드를 이해하기 위해서는 N-queens 코드의 알고리즘을 먼저 확실히 이해할 수 있어야 한다고 생각한다. 아래 코드는 다른 블로거의 N-queens 코드 중 가장 직관적이라고 생각했던 코드이다. (해당 코드는 '시간 초과' 이슈 발생)

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)