N-queen 문제

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

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

---

입출력 예nresult

4

2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

 

# 해결 방법

from copy import deepcopy
cnt = 0
def back_tracking(arr, idx, n):
    global cnt
    lst = set([i for i in range(n)])
    for k in range(idx):
        lst.discard((arr[k] - (idx - k)))
        lst.discard((arr[k] + (idx - k)))
        lst.discard(arr[k])
        # print(arr)
        # print(idx, list(lst))
    for j in list(lst):
        if idx+1 == n:
            cnt += 1
        else:
            new_arr = deepcopy(arr)
            new_arr[idx] = j
            back_tracking(new_arr, idx+1, n)

        # if all((arr[k] - (idx - k)) != i and (arr[k] + (idx - k)) != i and arr[k] != i for k in range(idx)):
        #     if idx+1 == n:
        #         cnt += 1
        #     else:
        #         new_arr = deepcopy(arr)
        #         new_arr[idx] = i
        #         back_tracking(new_arr, idx+1, n)


def solution(n):
    global cnt
    answer = 0
    arr = [-1] * n
    back_tracking(arr, 0, n)

    return cnt

 

사실 이 문제를 풀이하는 방식은 많지만, 일차원 배열로 푸는 방식을 채택했다.

 

처음에는

1. backtracking 방식으로

2. 매번 하나씩 넣을 때마다 겹치는 부분이 있는지 검증하고, 다음 재귀를 실행할지 말지를 결정한다.

 

이렇게 하니, 생각보다 시간 복잡도가 많다는 생각이 들었다.

 

그래서

3. set를 만들어서 0-(n-1) 까지를 넣고 이전의 채워 넣었던 숫자별로 검증해서 set에서 삭제하고, 해당 부분만 재귀를 돌리게 된다.

 

 

이렇게 되면 n*(n-1)*3이었던 탐색 시간을 (n-1)*3 + set에서 삭제하는 시간으로 변하게 되는데 더 빠른 시간으로 풀 수 있다.