[백준 9663] 백트래킹 대표 문제 N-Queens

체스를 모르는 나에겐 문제 내용이 너무 부족했다. 서로 공격할 수 없는다는 게 어떤 건지 몰랐다.

체스도 모르고 백트래킹도 잘 모르니 유튜브에 검색하다가 좋은 강의 영상을 봤다.

자세하게 알려주고 기본 설명과 구현, 두가지 영상으로 나뉘어있다.

 

주니온TV아무거나연구소 - 파이썬으로 배우는 알고리즘 기초: 18. 백트래킹과 n-Queens 문제

 

 

문제 설명을 간단히 하자면, 크기가 N*N인 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 방법의 수를 구하는 문제다.

이 때, 퀸은 다른 걸 공격할 수 없도록 같은 행, 열, 대각선 외의 위치에 놓아야 한다.

 

(x1,y1), (x2,y2)가 있을 때 |x1-x2| = |y1-y2| 면 같은 대각선상에 있다.

---

풀어본 결과, 내 결론은 파이썬으로 푸는 건 거의 불가능하다.

최대한 내 힘으로 해보려고 했지만 자꾸 시간초과로 실패해서 서치해보니, 파이썬으로 백트래킹 문제는 시간복잡도상 권장하지 않는다고 한다.

실제로 파이썬으로 다들 얼마나 맞았나 채점현황을 봤는데 길이 105자 코드들이 정답을 맞춘 것으로 보인다.

이것의 진실은 이 문제를 서치했을 때 가장 처음에 나오는 글에 야매코드가 있다 ㅋㅋㅋ (정답을 알아내서 리스트 출력하는 방법)

그 코드 길이가 105자더라...

나도 잠시 고민했지만 그냥 마음편히 실패로 놔두기로 결정했다.

 

def nq(col,i=0):
    global c
    n = len(col)-1
    if promising(i,col):
        if i==n:
            c += 1
        else:
            for j in range(1, n+1):
                col[i+1] = j
                nq(col,i+1)

def promising(i,col):
    k = 1
    flag = True
    while k<i and flag:
        if col[i]==col[k] or abs(col[i]-col[k])==(i-k):
            flag = False
        k += 1
    return flag

col = [0]*(int(input())+1)
c=0
nq(col=col)
print(c)

 

위의 영상의 코드에서 조금 바꾼 코드다. 답은 다 맞지만 시간 초과로 성공하진 못했다.

어쨌든 풀어보려고 영상도 보고 코드도 보고 하니 백트래킹에 대해 좀 더 이해할 수 있던 좋은 시간이었다.