(프로그래머스) N-Queen

문제 설명

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

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

 

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

 

제한사항

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

---

입출력 예

n	result
4	2

입출력 예 설명

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

 

 

소스

def check(r, row):
    # 이전 행에 놓았던 모든 퀸 확인
    for i in range(r):
        # 값이 같다는 의미는 열이 같다는 의미이므로 둘수 없음
        if row[r] == row[i]: 
            return False
        # (값 - 값 == 열 - 열) 이 값이 같다는 의미는 대각선에 존재한다는 뜻
        # 즉 비교할 행 간의 차이와, 열 간의 차이가 같다면 대각선에 존재한다는 의미이다.
        if abs(row[r] - row[i]) == r - i:
            return False
    
    return True
        

# 해당 r에 대해서 확인한다.
def queen(r, n, row):
    global answer
    
    # 마지막 행까지 확인했으면 +1
    if r == n:
        answer += 1
    else:
        # r번째 행의 각 열에 퀸을 둔다고 가정한다.
        for c in range(n):
            row[r] = c
            # 해당위치에 퀸을 둬도 괜찮다면 다음행으로.
            if check(r, row):
                queen(r + 1, n, row)
            
            
def solution(n):
    global answer
    
    answer = 0
    row = [0] * n # 인덱스가 행이고 값이 열이다.
    queen(0, n, row)
    
    return answer