백준 9663 : N-Queen (파이썬)

N-Queen

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
10 초	128 MB	56281	28251	18511	49.675%

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92

---

코드

# https://teching.tistory.com/
n = int(input())
cnt = 0
def nQueen(placed):
    global n, cnt
    row = len(placed)
    if row == n:
        cnt += 1
    else:
        #해당 열에서 퀸을 둘 수 있는 곳을 찾기.
        can = [1 for i in range(n)]
        for i in range(row):
            can[placed[i]] = 0
            #대각선
            if placed[i]+(row-i) < n :
                can[placed[i]+(row-i)] = 0
            if placed[i]-(row-i) >= 0 :
                can[placed[i]-(row-i)] = 0
        #다음 체스말 두기
        for i in range(n):
            if can[i]:
                placed.append(i)
                nQueen(placed)
                placed.pop()

nQueen([])
print(cnt)

해설

백트래킹하면 꼭 등장하는 문제이다.

처음에는 모든 경우의 수를 다 확인을 해주었다. 당연하게도 시간 초과가 발생했다.

그래서 시간을 어떻게 하면 줄일 수 있을까 고민해봤다.

 

고민해본 결과 한줄에 퀸이 한 개는 무조건 들어가도록 퀸을 배치하면 될 것 같았다.
왜냐면 N x N 크기의 체스판에 퀸 N개를 놓는 문제인데 퀸은 가로 세로 대각선을 공격할 수 있으므로 서로 공격받지 않도록 두려면 같은 열에 두는 것을 피하려면 N개의 열에 하나씩 두는 방법뿐이었다.

즉, 한열에 한 개도 둘 수없다면 실패한 경우의 수라는 소리다.

 

최종적으로 내가 짠 알고리즘을 간략하게 설명하자면

1. 해당 열에 퀸을 둘 수 있는 위치를 계산함.
   이전에 두었던 퀸들을 이차원 배열이 아닌 1차원 배열에 저장해줌(배열의 인덱스가 열이 됨)
   (예로 placed 배열에 [0, 3, 1]이 저장되어 있다면 차례대로 0번째 3번째 1번째에 퀸이 올라가 있는 것이다.)
   이제 이전에 뒀던 퀸들의 위치를 기반으로 현재 열에서 공격받지 않는 자리를 계산함
2. 둘 수 있는 곳에 퀸을 두고 다음 열로 넘어감
3. 넘어간 열에서 퀸을 둘 수 없다면 다시 1번으로 돌아간뒤 2번에서 둔곳이 아닌 다른곳에 퀸을 둬봄
4. 1~3 과정을 반복하며 모든 경우의 수를 확인하고 n개의 퀸을 모두 둔 경우를 세어줌.

내가 짠 알고리즘을 표현한 애니메이션이 있어 가져왔다.

아래 애니메이션을 보면 알고리즘의 과정에 대해 쉽게 파악할 수 있다! ( 첫번째 경우의수를 확인하기까지의 과정)

이와같은 과정을 첫번째 열에 퀸을 모두 둬보며 반복한다!

출처 :&nbsp;https://ko.wikipedia.org/wiki/%EC%97%AC%EB%8D%9F_%ED%80%B8_%EB%AC%B8%EC%A0%9C