N-Queen

시간이 조금 있어서 전에 풀다가 포기했던 N-Queen 문제를 풀어보려고 한다.
https://school.programmers.co.kr/learn/courses/30/lessons/12952

여기서 주의해야할 점은 2차 배열을 사용하면 시간초과가 나니 1차 배열과 백트래킹을 사용해야 한다는 점이다. 어차피 한 행당 들어갈 수 있는 퀸은 한 개니 1차 배열을 사용해서 가로와 세로의 경우의 수를 없애줘야 한다.

그리고 백트래킹과 dfs 를 사용해야 한다고 한다. 나는 제일 직관적인 재귀로 백트래킹을 구현해보려 한다.

참고 글
https://school.programmers.co.kr/questions/24716

answer = 0
def solution(n):
    # answer 

    for i in range(n):
        visited = []
        dfs(visited, (0, i), n)
        
        
    return answer


def dfs(visited, index, n):
    global answer
    
    near = [(index[0]+1, i) for i in range(n)]

    if visited != [] and index[0] <= visited[-1][0]:
        del visited[index[0]:]
        
    
    if index in visited: # 이거 때문에 for 문이 작동을 안 함 
        return
    
    visited.append(index)

  # 인접 노드 추가하기
    for i in visited:
        
        # 수직 방향 칸 제거
        next = index[0] + 1
        if (next, i[1]) in near:
          
          near.remove((next, i[1]))

        val = index[0] - i[0] + 1

        
        # 다음 행에 있는 대각선 칸 인덱스
        rem_i1 = i[1] + val 
        rem_i2 = i[1] - val 
          
        # 배열의 범위 내에 있다면 인덱스 제거
        if (next, rem_i1) in near:
          near.remove((next, rem_i1))
          
        if (next, rem_i2) in near:
          near.remove((next, rem_i2))
          
    
    
    if len(visited) == n:
      answer += 1

    if near == []: # 탐색이 끝나면
      return 
    
    for i in near:
      dfs(visited, i, n)
            
    
print(solution(8)) # 92

다 짜놓고 answer 을 어떻게 return 해야할지 몰라 애를 먹었다. 결국 전역 변수로 선언해서 하긴 했는데... 솔직히 맘에 안 든다 ^ㅠ 이 부분은 조금 더 생각해봐야 겠다.