파이썬 백준 9663 N-Queen

n = int(input()) stack = 0 Qlist = [] def Qcheck(Qlist, Q) :     for i in range(len(Qlist)) :         if Q == Qlist[i] or abs(len(Qlist) - i) == abs(Q - Qlist[i]) :             return False     return True def DFS(Qlist, Q) :     global stack     if len(Qlist) == n - 1 :         if Qcheck(Qlist, Q) :             stack = stack + 1     if Qcheck(Qlist, Q) :         for i in range(n) :             DFS(Qlist + [Q], i) if n < 12 :     for i in range(n) :         DFS([], i) elif n >= 12 and n%2 == 0 :     for i in range(n//2) :         DFS([], i)     stack = stack * 2 else :     for i in range(n//2) :         DFS([], i)     stack = stack * 2     DFS([], n//2) print(stack)

재귀함수를 짰는데 이게 아무튼 DFS라는것같다

사람이 경우의수 세듯이 결과 건질때까지 파고들어갔다가 건지고나면 다음 경우로 넘어가면서 count를 세면 DFS고,

인간미없게 모든 경우의수를 횡렬로 전개하다가 작업 막바지쯤부터 count에 걸리는 조건이 계속 나오면서 하베스트하면 BFS인가 대충 그런 느낌?

DFS는 인간의 방법이랑 비슷해서 직관적인데 재귀 깊이가 무한한 경우에 걸리면 영원히 안끝나고, BFS는 솔직히 뭐라는건진 모르겠는데 깊이의 level이 일정선에 머무르면서 한단계씩 넘어가니까 적당히 컷하기 좋을 것 같다.

 

1. 이미 놓여진 Qlist가 주어졌을때 새로운 퀸을 위치 Q에 놓는 것이 유효한지 판별하는 함수 Qcheck(Qlist, Q) 정의

2. Qcheck가 True면 Qlist에 Q를 놓고 다시 자신을 실행하며, Qlist가 체스판 길이 n에 도달하면 반복을 멈추고 stack을 +1하는 재귀함수 DFS(Qlist, Q) 정의

3. 체스판의 각 위치에 첫번째 퀸을 놓고 DFS를 돌려준 뒤 stack을 건진다.

 

첫번째 제출시 시간초과가 떠서 해의 대칭성을 이용해 최적화를 했다.

체스판 길이가 짝수면 절반까지만 돌리고 stack을 2배

체스판 길이가 홀수면 가운데줄 전까지 돌리고 stack을 2배, 마지막으로 아직 안해본 가운데줄에서 DFS를 실행

 

 

def Qlist_levelUP(Qlist_level_n, Q) :     check = 1     Qlist = Qlist_level_n[:]     if Q in Qlist :         check = 0     for i in range(len(Qlist)) :         if abs(len(Qlist) - i) == abs(Q - Qlist[i]) :             check = 0     if check == 1 :         Qlist.append(Q)         return Qlist     else :         return [0] # level n의 Qlist에서 다음 n+1번째 퀸을 Q값에 뒀을때 # 유효하면 level n+1의 Qlist를 출력, 무효하면 [0] 출력 n = int(input()) answerlist = [[] for i in range(n)] # level 1의 answerlist 생성 for i in range(n) :     answerlist[0].append([i]) # level x의 answerlist를 참고하여 level x+1의 answer를 작성 # level n이 될때까지 for x in range (0, n-1) :     for Qlist in answerlist[x] :         for Q in range(n) :             if Qlist_levelUP(Qlist, Q) != [0] :                 answerlist[x+1].append(Qlist_levelUP(Qlist, Q)) # level n의 해의 갯수 출력 print(len(answerlist[n-1]))

재귀 컨디션 생각하기가 힘들어서 처음에 짠 코드는 길이 2짜리 리스트를 만들고

[0]에 퀸 i개 놓은 해 담고, 그걸 참고해 [1]에 i+1번째 퀸까지 놓은 결과를 담은다음 [0]에 덮어씌우는걸 n번 반복했는데

한 n=12정도까진 잘 나오다가 주어진 최댓값 n=14를 치니 터미널이 영원히 멈췄다...

경우의 수를 세라하면 얌전히 수만 세고 쓸데없이 과정을 남기진 말아야 메모리와 시간이 절약된다는 교훈