N-Queen 알고리즘

-조건

 

• 각 열에 하나의 퀸만 존재
• 각 행에 하나의 퀸만 존재
• 퀸의 대각선에 다른 퀸이 존재할 수 없음

 

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


def n_queen(li, n, queens):
    result = 0
    if n == queens:
        return 1

    for i in range(queens):
        li[n] = i
        if check(li, n):
            result += n_queen(li, n + 1, queens)
    return result


N = int(input())
arr = [0] * N

print(n_queen(arr, 0, N))

처음에 2차원 배열로 만들어야 하나 생각을 하다가 도저히 떠오르지 않아서 찾아보게 되었습니다. 

리스트 1줄로 만드는 것이여서 처음에 코드를 하나하나 뜯어서 어떻게 실행이 되나 확인하는데 시간이 많이 걸렸습니다.

리스트안의 값들이 열을 의미하고 같은 값이 되면 같은 행에 존재하게 되어서 False를 반환을 해줍니다. 또한 대각선 값을 구하는 공식이 행간 거리와 열간 거리가 같으면 대각선이 므로 제외해야 합니다. 하지만 대각선이 남서쪽과 남동쪽 2방향이 존재하므로 절대값을 사용하여 같게 되면 False값을 반환합니다. True일 경우 다음 행으로 넘어가서 열을 하나하나 검사하여 모두 True값을 반환하면 결과값에 1을 더하는 방식임을 알게 되었습니다.