[백준 #9663] N-Queen - 파이썬 (python)

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

 

문제를 보자마자 무슨 뜻인지는 알겠는데

구체적으로 어떻게 구현을 해야 할 지 너무 막막했다.

 

백트래킹 알고리즘에서 아주 유명한 알고리즘이라

다른 블로그를 참고하여서 이해했다.

 

def nqueen(sol,N):
    global count
    if len(sol)==N:
        count+=1
        return 0
    candidate=list(range(N))
    for i in range(len(sol)):
        if sol[i] in candidate:
            candidate.remove(sol[i])
        distance=len(sol)-i
        if sol[i]+distance in candidate:
            candidate.remove(sol[i]+distance)
        if sol[i]-distance in candidate:
            candidate.remove(sol[i]-distance)
    if candidate!=[]:
        for i in candidate:
            sol.append(i)
            nqueen(sol,N)
            sol.pop()
    else:
        return 0
    
count=0
N=int(input())
for i in range(N):
    nqueen([i],N)
print(count)

일단 이렇게 되어 있어서 하나하나 이해하는데 시간이 걸린 것 같다.

 

단순하게 같은 열, 행, 대각선에는 서로 다른 퀸을 놓을 수 없다는 것은 알겠는데,

대체 어떻게 구현해야 할 지 감이 안잡혔다.

 

코드를 보면서 이해한 내용으로는

어차피 같은 행, 열에는 놓을 수 없으니까

굳이 2차원 배열로 좌표처럼 구현하지 않고

한 열이나 행을 기준으로 1차원 배열로도 충분히 구현할 수 있는 것 같다.

 

정답제출을 하니까 시간초과로 나와서 pypy3로 제출하니까 정답처리됬다.

python3로 구현하면 어쩔 수 없이 시간초과가 난다는데,

그럴거면 이런 문제를 왜 냈는지 이해불능