프로그래머스 [lv4] N-Queen 파이썬

문제 설명

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

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

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

 

제한사항

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

---

입출력 예

n	result
4	2

 

---

접근

- N-Queen은 유일한 백트래킹 문제에 해당

- 모든 경우의 수를 count 하면서, 필요없는 부분을 가지치기한다.

- 백트래킹은 n이 작을 때(문제조건: n <= 12) or 어쩔 수 없이 모든 경우의 수를 구해야 할 때 사용한다.

=> 백트래킹은 재귀 구조를 사용한다.

 

구하고자 하는 것

- 조건을 만족하는 경우의 수  !=  조건을 만족하는 체스판의 형태

- 조건을 만족하는 체스판의 형태가 어떤 모습인지 구할 필요가 없다 ==> 조건을 만족하는 경우의 수만 카운트하여 return

 

풀이 코드

 

def solution(n: int):
    return search([0] * n, 0)


def search(queen: list, row: int):
    n = len(queen)
    count = 0

    if n == row:
        return 1

    for col in range(n):
        queen[row] = col
        if check(queen, row):
            count += search(queen, row + 1)
    return count


def check(queen: list, row: int):
    for i in range(row):
        if queen[i] == queen[row] or abs(queen[i] - queen[row]) == row - i:
            return False

    return True

 

 

 

 

search() 함수: 재귀 구조로 작성

인자: 각 row에 해당되는 queen 변수: list ,  각 row의 번호 (0, 1, 2 ... n )

# 재귀 함수 => 탈출구가 있어야한다. (if n == row)
def search(queen, row):
    n = len(queen)
    count = 0

    if n == row:
        return 1

    for col in range(n):
        queen[row] = col  # row, col 영역에 퀸을 배치
        if check(queen, row):
            count += search(queen, row + 1)  # 다음 열로 퀸을 넘긴다.
    return count  # 배치할 수 있는 방법의 수 리턴

 

check() 함수

def check(queen, row):
    for i in range(row):
        if queen[i] == queen[row] or abs(queen[i] - queen[row]) == row - i:
            return False
    return True

위 그림에서 보듯, row - i 와 queen[row] - queen[i] 의 값이 같다는 것은 동일 대각선 상에 있음을 뜻한다.

queen[i] == queen[row] 가 뜻하는 바는, 하나의 행에서 같은 열에 위치함을 의미.

 

즉 위의 두 조건 중 하난를 만족하면 false를 return