백준 9663 N-Queen

https://www.acmicpc.net/problem/9663

 

 이 문제는 전통적인 알고리즘 문제이다. 이 문제를 푸는 법은 결국엔 하나하나 다 놔봐서 되는 경우의 수를 찾는 백트랙킹으로 풀어야한다.

 

 먼저 우리는 1행을 기준으로 아래행으로 나아가면서 퀸을 하나하나 놔 볼것이다. 근데 퀸이 서로를 겨누게 두면 안 되기에, 다른 퀸과 같은행,같은열,같은 대각선에 두면 안된다. 같은행은 우리가 행을 내려갈 것이므로 크게 신경 쓰지 않아도 되고, 같은 열은 그냥 검사하면 되고, 같은 대각선은 체스 보드판을 일종의 좌표계로 보고 x+y=t, x-y=t에 걸리는지 아닌지를 검사하면 된다.

 

 본래 필자는 이를 2차원 배열로 직관적으로 풀려했으나, 0,1을 하나하나 건드려야 한다는점, 메모리가 부족하단 점 등 때문에 x행y열의 퀸을 x,column[x]로 표현하기로 했다. 예를 들어 1행에 있는 퀸의 위치를 알고 싶다면, column[1]을 살펴보고, 뭐 column[1]==2라면, 1행의 퀸은 2열에 있는 것이다. 

 

 이런 식으로 행을 나아가며, 그 전까지의 행들의 퀸을 하나하나 비교해가며, 같은 열에 있는지, 같은 대각선에 있는지를 검사해가며 나아가면 된다. 

 

n=int(input())

ans=0
column=[0]*(n+1)

def promising(x):
    for i in range(x):
        if (column[i]==column[x]) or (abs(column[x]-column[i])==abs(x-i)):
        #같은 열에 있느냐/같은 대각선에 있느냐
            return False
    return True

def finding_Q(i):
    global ans
    if i==n:
        ans+=1
        #마지막 행이니 끝
        return
    for j in range(n):
        column[i]=j
        #일단 이렇게 두고 다음 행으로 나아간단 감각
        if promising(i):
            finding_Q(i+1)

finding_Q(0)
print(ans)

 

 위의 문제를 파이썬으로 그대로 내게된다면, 시간초과가 뜨게 되므로 PyPy로 내야한다. 

 

 필자는 이 문제를 제대로 풀지 못하여 https://seongonion.tistory.com/103 이 블로그 글을 참고하여 문제를 풀었다