[Programmers]Lv 3. N-queen

문제:

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

 

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

ㅜ=4일 때

 

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

 

풀이 방법:

 되추적 방법을 사용하는 대표적인 예시인 문제이다. 따라서 queens에서는 각 col별로 queen을 배치하는데 우선 promising이라는 함수에서 이전에 배치한 col을 기준으로 해당 인덱스에 queen을 배치할 수 있는지 판단해준다. 모든 방법을 다 판별해주는 방법도 생각할 수 있지만 그럴 경우 n이 커짐에 따라 많은 시간이 발생할 것이다. 따라서 promising이라는 되추적 판단을 해주는 함수로 인해서 많은 시간을 단축 할 수 있었다.

def promising(i,col):
    k=0
    correct=True
    while (k<i and correct):
        if (col[i]==col[k] or abs(col[i]-col[k])==i-k):
            correct=False
            break
        k+=1
    return correct
 
def queens(n,i,col,count):
    if (promising(i,col)):
        if (i==n-1):
            count.append(col)
        else:
            for j in range(n):
                col[i+1]=j
                queens(n,i+1,col,count)
def solution(n):
    col=n*[0]
    global count
    count=[]
    queens(n,-1,col,count)
    return len(count)

 

문제 링크:

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