[Algorithm] N-Queen

프로그래머스 N-Queen 문제

: 일단 과거에 코드스테이츠에서 거의 똑같은 문제를 단순히 알고리즘 문제 풀이 말고, 좀 다른 방식으로 푸는 세션을 했던 것 같은데.. 어쨌든 한번에 못풀고 헤맸다.

문제 해석

: 체스의 퀸이 갈 수 있는 방향은 왼쪽, 오른쪽, 위쪽, 아래쪽, 대양옆 대각선이고 거리는 자유이다. 이러한 룰을 바탕으로 NN 크기의 체스판에 N개의 퀸을 배치하는데, 조건이 각각의 퀸이 서로를 죽일 수 없는 위치에 있어야한다는 것이다. 즉, 1번째 퀸이 A에 있다면 2번째 퀸은 1번 퀸의 공격 범위 내에 없어야한다는 것. 그렇게 N개의 퀸을 NN 크기의 체스판에 서로 공격할 수 없게 배치할 수 있는 경우의 수를 구하는 것이 이 문제의 요구사항이다.

문제 설계

: 일단 처음 그냥 떠오른건 분명히 몇번하다보면 규칙이 나올 것 같아서 DP나 재귀함수를 이용한(DFS 백트랙킹이라고 하더라 블로그에서는..) 탐색으로 풀어야겠다는 생각이었다. DP를 먼저 시도해보다가 너무 사이즈가 커서(초반에 몇개는 다 0이고..) 후자의 방법을 선택했다. 재귀함수를 이용해서 문제를 푼다고 생각해보면,

• 먼저, 한개의 행씩 탐색하면 된다. 퀸의 전진 가능 범위를 보면 결국 같은 행에는 하나의 퀸만 올 수 있음을 알 수 있기에 각 행마다 하나의 퀸을 배치하고 => 다음 행으로 넘어가서 놓을 수 있는 곳을 찾는 방식을 이용하는거다.

• 그러면 한개의 행에 퀸을 각각 둬본다고 할 때, 퀸을 둔 다음에는? 그 퀸이 이동할 수 있는 범위에 모두 False를 한다. 이전에 chess판을 형상화(?)한 이중배열을 만들어놨다고 가정한다. 그리고 탐색을 하면서 퀸을 놓는 자리와 더불어 퀸의 이동범위 모두에 False를 해둔다(디폴트로 True가 돼있다고 생각).

• 그렇게 다음 행으로 넘어가면 이전에 False를 처리해둔 곳에는 못놓게 하다보면 두번째 행에서 둘 수 있는 곳을 찾을 수 있다. 그러면 똑같이 그곳의 퀸이 갈 수 있는 범위 모두를 False처리 하고 똑같이 다음 행으로 넘어간다. 이렇게 재귀함수를 통해 반복하다보면 마지막 행까지가게되고(그러나 만약 중간에 어떤 자리에도 퀸을 놓을 수 없는 행이 있으면 그 케이스는 거기서 cut이다. 이래야 DFS가 되고, 완전탐색을 안한다), 그렇게 N개를 모두 배치했다면 최종 answer(구하고자 하는 케이스의 수)에 +1을 해준다.

  
  cnt = 0
  depth = 1
  answer = 0
  board = []
  def solution(n):
      
      global board
      global depth
      global cnt 
      global answer
  
      for i in range(n):
          board.append([None]+[True for j in range(n)]+[None])
      board = [[None for i in range(n+2)]] + board + [[None for i in range(n+2)]]
  
      def queens_road(copy_board, num) :
  
          for k in range(1,n+1):
            if copy_board[k][num[1]] is not None:
              copy_board[k][num[1]] = False 
            else:
              break
          for k in range(1,n+1):
            if copy_board[num[0]+k][num[1]+k] is not None:
              copy_board[num[0]+k][num[1]+k] = False
            else:
              break
          for k in range(1,n+1):
            if copy_board[num[0]-k][num[1]+k] is not None:
              copy_board[num[0]-k][num[1]+k] = False
            else:
              break
          for k in range(1,n+1):
            if copy_board[num[0]+k][num[1]-k] is not None:
              copy_board[num[0]+k][num[1]-k] = False
            else:
              break
          for k in range(1,n+1):
            if copy_board[num[0]-k][num[1]-k] is not None:
              copy_board[num[0]-k][num[1]-k] = False
            else:
              break  
  
      # 재귀함수를 만들 것
      # 끝에가서 n번을 찍었는지를 체크해야함 
       
      limit_line = [[None for i in range(n+2)]]
  
      def recursion(arr) :
          global depth
          global cnt 
          global answer
  
          if cnt == n:
              answer += 1 
              return 
          
          for idx, el in enumerate(arr[depth]):
              if el is None:
                  continue
              elif not el :
                continue
              elif el :
                  copy_board = []
  
                  for i in range(1,len(arr)-1):
                    new_arr = []
                    for j in range(1,len(arr)-1):
                      new_arr.append(arr[i][j])
                    copy_board.append([None]+new_arr+[None])
                  copy_board =  limit_line + copy_board + limit_line
  
                  queens_road(copy_board, (depth,idx))
                  depth+=1 
                  cnt+=1 
                  recursion(copy_board)
                  cnt-=1 
                  depth-=1 
  

recursion(board)
return answer

: 처음엔 위의 방법으로 풀었는데, 문제가 한두개가 아니었다.. 일단 시간복잡도에 걸려서 통과는 못했다.

1차시도 결과 문제점

• 체스판을 형상화하여 진행하기 때문에 매 시행마다 복사본을 만들어야함. 하지만 이것도 꽤나 많은 시행이 이뤄짐
• 양옆 대각선, 열에 False를 찍는 시행이 너무 많음. 그리고 이걸 여러번 해서 시간복잡도가 매우 비효율적임

개선해야할 사항

• 일단 chess판을 안만들고 진행하는 방향으로 가야함.
• 배치하는 퀸마다 공격범위를 False로 하는 방식보다는 퀸을 배치하려는 곳의 대각선 양옆 및 열에 다른 퀸이 있는지를 보는 관점이 더 나은 것 같다.
• 대각선 양옆 및 열을 구하는 더 효율적인 방법이 필요함

정답 코드

cnt = 0
depth = 0
answer = 0
col = set([])
way2 = set([])
way1 = set([])

def solution(n):

    global depth
    global cnt 
    global answer


    def recursion() :
        global depth
        global cnt 
        global answer
        global col
        global way1
        global way2

        if cnt == n:
            answer += 1 
            return 

        for idx in range(n):
              if idx in col or depth-idx in way2 or depth+idx in way1:
                continue
              else:
                col.add(idx)
                way1.add(depth+idx)
                way2.add(depth-idx)
              depth+=1 
              cnt+=1 
              recursion()
              depth-=1 
              cnt-=1 
              col.remove(idx)
              way1.remove(depth+idx)
              way2.remove(depth-idx)

        return answer
    
    return recursion()

: 결국 체스판도 없앴고, 대각선 양옆 및 열을 구하는 더효율적인 방법을 찾아냈지만..힌트를 너무 많이 봤다...ㅎ

푼 방법 및 마무리

• 같은 행에는 없다는 전제이기에 열, 대각선 양옆에 또다른 퀸이 있는지 확인 후에 없으면 그 자리에 배치한다는 관점으로 접근
• 이 때, 배치를 하면 해당 열 정보(y값)을 배열에 담고, 그 다음부터 y값이 배열에 있다면 열이 겹치는 것임. (열에 겹치는 퀸이 있는지를 판별하는 더 효율적인 방법)
• 또한, 배치를 하면 대각선 양옆 정보도 담는데.. 이거는 내가 생각못했다. 예를 들어, (3,3), (4,4), (5,5) 혹은 (1,2), (2,3), (3,4) 등을 보면, 공통적으로 각각 x,y축을 뺀 값이 같다. 결론적으로 대각선 중에 왼쪽위에서 오른쪽 아래로 내려가는 형태의 대각선이 동일선 상에 있다면 x,y값을 뺀 값이 같을 것이다. 그래서 대각선 정보도 열 정보처럼 배열에 담아두며 다음에 이것과 같은 값이 나오면 겹치는 것으로 처리한다. (오른쪽 위에서 왼쪽 아래로 내려가는 구조의 대각선은 (0,4), (1,3), (2,2) 등 x,y값을 더한 값이 같다는 점을 이용한다)
• 위의 3정보를 바탕으로 문제를 풀면 chess_board를 이중 배열로 만들어가면서 False를 체크하고 복사하고 등의 과정이 필요없게되고, 겹치는 부분을 탐색할 때 직접 다 찾아보지 않아도 더 빠르게 찾을 수 있다.

: DFS + 백트래킹까지 생각해내서 완전탐색을 피했고, 행 단위로 탐색하는 것까지 다 잘찾았는데.. 항상 구현 문제를 풀 때 배열을 만들어서 거기서 체크하면서 만들었어서 그런가 board를 안만들고 푸는 방법을 떠올리지 못했고, 대각선 부분이 겹치는지 파악할 때 정답과 같은 방법을 떠올리지 못했다.