백준 9663 풀이 (백트래킹, 재귀함수)

사실 어제 풀다가 안풀려서 포기했다. 어제 짠 코드는 모든 경우를 다 확인하다보니 시간도 오래걸리고, 무엇보다 중복이 생겼다. 그래서 그냥 시원하게 던져버리고 오늘 다시 풀어보았다.

오늘은 접근을 달리했다. N * N개의 판에서 퀸이 4개가 들어가야한다고 하는데 이는 결국 각 행마다 퀸이 딱 하나씩 들어가야한다는 소리다.

즉, 무조건 배열이 [[0,?], [1,?], [2,?], [3,?] ......[n-1,?]] 이런 방식이면 되는거다. 따라서 이를 토대로 코드를 짰다.

N = int(input())

sum = 0
def queen(tlist,n):
    global N
    global sum
    if len(tlist) == N:
        sum+=1
        return
    
    for i in range(N):
        check = 0
        for ban in tlist:
            mi =  n - ban[0]
            if ban[1] == i or [n,i] == [ban[0]+mi,ban[1]+mi] or [n,i] == [ban[0]+mi,ban[1]-mi]:
                check = 1
                break
        if check == 1:
            continue
        tlist.append([n,i])
        queen(tlist,n+1)
        tlist.pop()
queen([],0)
print(sum)

여기서 문제는 python3로 제출하면 시간초과가 난다. 다른 고수님들의 블로그를 보니 재귀함수 자체가 파이썬과는 잘 안맞는다고 한다. claude-u.tistory.com/245

#196 백준 파이썬 [9663] N-Queen

즉, 시간복잡도상 백트래킹 문제 같은 경우는 c++을 사용하는게 좋다는 의견이다.

물론 나는 꼼수를 써서 python3가 아닌 pypy3로 제출을 해버렸다. pypy3가 정말 빠르다.

 

결론을 맺자면, 백트래킹 너무 어렵다.