[프로그래머스] N-Queen

https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen

 

1차원 list를 활용한 searching 문제입니다. 

문제부터 간단하게 요약하면, 

위 그림 같이 n x n 의 체스판 위에 Queen을 서로가 서로를 공격하지 않도록 배열하는 가짓수를 return 하는 것이 목표인 문제입니다. 

 

즉

solution(n)에 

n : 체스판의 가로, 세로의 세로길이(체스판은 정사각형)

이 input으로 들어갈 때

 

총 몇가지 배열이 나올 수 있는가를 return해야 합니다. 

 

<Solution 1-오답>

가장 간단한 아이디어는 2D array를 구성하여 해결하는 것입니다. 

 

예를 들어 설명하면 solution(3)의 case를 생각해봅시다. 

row의 index로 가능한 값은 [0,1,2] 

column의 index 또한 가능한 값은 [0,1,2] 입니다.

 

이중에서 처음 [0,1] 을 뽑았다고 생각하면, 각각의 가능한 index에서 뽑은 값을 없애줍니다.

row의 가능한 index = [1,2]

column의 가능한 index = [0,2]

 

이렇게 순차적으로 서로 공격하지 않는지를 check하면서 비워나가면서 searching을 하도록 구현하면 됩니다. 

실제 구현은 다음과 같습니다. 

import copy, math
def solution(n):
    global count
    global sorted_array
    count = 0
    sorted_array = []
    def search(candidate_list_row,candidate_list_column, pick_list):
        global count
        global sorted_array
        # print(candidate_list_row,candidate_list_column, pick_list)
        if len(pick_list) == n:
            if sorted(pick_list) not in sorted_array:
                sorted_array.append(pick_list)
                count+=1
            return
        
        for row_index, row_candidate in enumerate(candidate_list_row):
            for column_index, column_candidate in enumerate(candidate_list_column):
                new_pick = [row_candidate, column_candidate]
                if len(pick_list) == 0:
                    new_candidate_list_row = candidate_list_row[:]
                    del new_candidate_list_row[row_index]
                    new_candidate_list_column = candidate_list_column[:]
                    del new_candidate_list_column[column_index]
                    new_pick_list = pick_list[:]
                    new_pick_list.append(new_pick)
                    search(new_candidate_list_row, new_candidate_list_column, new_pick_list)
                flag = 0
                for pick in pick_list:
                    if abs(pick[0]-new_pick[0]) == abs(pick[1]-new_pick[1]):
                        flag = 1
                        break
                if flag == 0:
                    new_candidate_list_row = candidate_list_row[:]
                    del new_candidate_list_row[row_index]
                    new_candidate_list_column = candidate_list_column[:]
                    del new_candidate_list_column[column_index]
                    new_pick_list = pick_list[:]
                    new_pick_list.append(new_pick)
                    search(new_candidate_list_row, new_candidate_list_column, new_pick_list)

    search(list(range(1,n+1)), list(range(1,n+1)), [])
    
    return count

하지만 이렇게 구현을 할 시, 중복되는 값들이 count될 뿐만 아니라 계속 list의 삭제를 하면서 timeout 되는 상황이 옵니다(List의 경우 index로 삭제하는 경우 time complexity = O(N)). 실제로 testcase중에 6-10이 timeout으로 failing함을 알 수 있습니다. 따라서 좀더 중복된 counting 없이 빠르게 count할 수 있는 방법을 찾아야 함을 알 수 있습니다. 

 

<Solution 2-정답>

Queen은 무조건 한 row에 하나만 올 수 있기에 1D array를 사용하고, array의 index가 row를 나타낸다고 생각하면, 체스판의 Queen 위치를 1D array로 표현할 수 있음을 알 수 있습니다. 

 

이러한 1D array를 사용하고, 1D array에 element가 끝까지 다 차는 경우에만 count를 1씩 올려주는 형태로 searching을 하였습니다. 또한 아직 조사하지 않은 element들은 set에 저장하여 조사를 완료하고 삭제할 때의 시간도 줄여주는 방식으로 코드를 진행시킨 결과 제한된 시간안에 모든 경우를 통과함을 알 수 있었습니다.

 

실제 구현은 아래와 같습니다. 

import copy
def can_place(current_array, new): # can_place([0,2], 1)
    new_index = len(current_array)
    for index, element in enumerate(current_array):
        if abs(new_index - index) == abs(new - element):
            return False
    
    return True
def solution(n):
    global count
    count = 0

    range_set = set(range(n))
    def recursive(current_array, available_set):
        global count
        if len(current_array) == n:
            count+=1
            return

        for i in range(n):
            if i in available_set and can_place(current_array, i):
                new_available_set = copy.deepcopy(available_set)
                new_available_set.remove(i)
                new_current_array = current_array[:]
                new_current_array.append(i)
                recursive(new_current_array, new_available_set)
            else:
                continue


    for i in range(n):
        current_array = [i]
        new_set = copy.deepcopy(range_set)
        new_set.remove(i)
        recursive(current_array, new_set)
    
    return count