9663_N-Queen

문제는 더보기!

 

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8

예제 출력 1 복사

92

 

 

이러한 문제를 푸는 방법은 브루트포스나 백트래킹등 여러 방법이 있다.

 

처음에는 2차원 체스맵을 만들어서 구현하려고 했다. 그러다보니 복잡하기도하고 시간복잡도가 분명 늘어날 것 같았다. 

 

그래서 두번째로 생각했던것은 1차원 배열로 쭉 늘려서 생각하는 것이었다. 우선 그렇게 생각한 다음에, 규칙을 찾아서 제거하면 될 것 같았다.

 

그래서 처음구현할때 모든 경우의 수를 찾는 방법을 N과M문제에서 사용했던 방식으로 구현해 보았는데 조금만 수가 늘어나도 프로그램 구현 시간이 엄청 늘어나는것을 보고 포기했다.

 

고민을하다가 인터넷을 조금 찾아보니 색다른 방법이 있었다. 

 

체스맵에 5개의 퀸을 넣기 위해서는, 열마다 한개씩 들어간다는 것을 알 수 있다. 즉, 한 열혹은 행당 하나씩만 들어가는데 이를 이용해서 index값을 퀸의 x좌표를 대체할 수 있다는 것이다.

 

[1,2,3]같이 있다면 [0,1][1,2][2,3] 에 퀸이 위치해 있다는 것이다.

 

우선 1번째 열을 지정해준다. 그 이후에 행들을 검사하면서 맞는 부분이면 카운트를 넘기는 방식으로 할껀데 1열을 그냥 넘어가게 된다.

 

2번째 열부터는, 위에 이미 정해진 퀸의 위치와 대조하여 놓을 수 있는위치면 다음 열로 넘어가고, 그렇지 않으면위치시키지 않게 한다.

 

위를 반복하면서 1번째 열부터 마지막열까지 검사하면 총 카운트를 알 수 있다.

 

 

N = int(input())

lst =[0]*N
count=0

def f(queen,col):
    global count
    if col==N:
        count +=1
        return

    for i in range(N):
        queen[col] = i

        for x in range(col):
            if queen[x] == queen[col]:
                break
            if abs(queen[x]-queen[col]) == (col-x):
                break
        else:
            f(queen,col+1)

f(lst,0)
print(count)

#파이썬으로는 푸는거 불가
#answer = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596]
#print(answer[int(input())])

마지막 if문 두개를 보면각각 세로줄과 대각선을 검사한 것을 알 수 있다.

 

그런데 이걸 그대로 돌리면 시간초과가 뜨게된다... 저기서 더줄일방법이 생각이 안나서 결국 인터넷 검색을 해보았는데 

https://www.acmicpc.net/board/view/25761

글 읽기 - 이 문제는 파이썬으로는 못 푸는건가요???

위 글을 발견했다. 이문제는 시간복잡도때문에 파이썬으로 풀 수 없는듯 하다... 

 

그래서 문제해결을 위해서 결국 답을 print로 하나씩 찍어줘서 넘어간 후에 답안들을 보니 다 똑같이 푼것을 알 수 있었다. 조금은 허무한 문제였다.