[엘리스] N-Queen

N-Queen

n x n 의 체스 판에 n개의 Queen을 놓으려 합니다. 이 때, 다음의 규칙을 반드시 따라야 합니다.

• 같은 행에 2개 이상의 Queen이 존재해서는 안됩니다.
• 같은 열에 2개 이상의 Queen이 존재해서는 안됩니다.
• 하나의 대각선에 2개 이상의 Queen이 존재해서는 안됩니다. 이는 ‘’ 방향의 대각선과 ‘/’ 방향의 대각선 모두에 대하여 해당되는 조건입니다. 예를 들어 n = 4 일 경우, 아래와 같이 Queen을 배치하는 것은 가능하지 않다.

왜냐하면 다음과 같이 조건 1, 그리고 조건 3에 반하기 때문이다. 

 

n = 4 일 경우에는 다음과 같이 Queen 을 배치할 수 있는 경우가 2가지 존재한다.

n이 주어질 때, nn개의 Queen을 배치할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. (1≤n≤10)

출력

n개의 Queen을 배치할 수 있는 경우의 수를 출력한다.

입력 예시 1

4

출력 예시 1

2

입력 예시 2

5

출력 예시 2

10

풀이

• itertools.permutations을 이용해서 모든 경우의 수를 만듬
  • (0, 1, 2, 3)의 경우, 첫번째 row에는 0번째 위치에 두번째 row에는 1번째 위치를 의미.
• 3가지 조건에 위배되는 지 확인
  • 단, 가로에 겹치는 지 세로에 겹치는 지는 확인할 필요가 없음
    • permutations를 만들면서 이미 겹치지 않게 만들어짐
  • 대각선을 확이하는 방법으로 배열의 길이를 2배로 늘려서 확인 (아래와 같이 계산이 됨)
    • 4x4의 경우 가능한 아래와 같이 대각선의 갯수는 왼쪽 아래방향 7개, 오른쪽 아래방향 7개임
    • diagonalCheck1과 diagonalCheck2를 만들어서 두 방향 모두 확인.
      
  • 예) (1, 0, 3, 2)의 경우

	Q
Q
			Q
		Q

diagonalCheck1

0

0

0

2

0

2

0

0

diagonalCheck2

0

2

0

0

0

2

0

0

자세한 과정

1. 첫번째 row에 대해

0

0

0

0

0

1

0

0

0

0

0

0

0

1

0

0

2. 두번째 row에 대해

0

0

0

1

0

0

0

0

0

0

0

0

0

1

0

0

3. 세번째 row에 대해

0

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

4. 네번째 row에 대해

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

0

5. 모든 과정이 끝난 후

0

0

0

2

0

2

0

0

0

2

0

0

0

2

0

0

import sys
import itertools

def isPossible(assignment, n) :
    diagonalCheck1 = [ 0 for i in range(n+n) ]
    diagonalCheck2 = [ 0 for i in range(n+n) ]

    for i in range(n) :
        diagonalCheck1[(assignment[i] - i) + n] += 1
        diagonalCheck2[(assignment[i] + i) - n] += 1

    for i in range(n+n) :
        if diagonalCheck1[i] >= 2 or diagonalCheck2[i] >= 2 :
            return False

    return True

def nQueen(n) :
    '''
    n개의 Queen을 배치하는 경우의 수를 반환하는 함수를 작성하세요.
    '''

    myList = [ i for i in range(n) ]
    myPermutation = itertools.permutations(myList)
    cnt = 0

    for assignment in myPermutation :
        if isPossible(assignment, n) == True :
            cnt += 1

    return cnt

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    n = int(input())

    print(nQueen(n))

if __name__ == "__main__":
    main()

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn