[BOJ] 9663 N-Queen - python

9663번: N-Queen

9663번: N-Queen

풀이

일단 체스판에 Queen을 두는 방법은 가로쭉,세로쭉,대각선쭉에 퀸을 두지 않는 것이다. 이것은 같은 행 혹은 같은 열에 Queen을 두지 않게 하고 + 대각선 검사 를 진행하면 된다. 행,열을 이차배열로 관리할까 했지만 어차피 한 행,열 당 하나씩 밖에 못 놓는 성질을 이용하여 행 혹은 열을 배열의 index로, 나머지 하나를 value로 관리하여 메모리를 줄인다. 0행을 기준으로 시작하여 0열,1열,2열...n-1열까지 queen을 넣으며 모든 경우의 수를 모두 시행한다. dfs 의 인자로 지금까지 queen이 놓여져있는 배열과, 다음 퀸이 들어갈 열을 넘겨 조건을 검사한다.

import sys
sys.setrecursionlimit(10**5)

N = int(sys.stdin.readline().rstrip())

# 퀸이 놓여져 있을 때 가로,세로,대각선 방향에는 퀸이 놓여지면 안됨
# = 각 행에는 딱 하나만 놓을 수 있음

answer = 0

def dfs(queen,next_queen):
    global answer
    #종료조건
    #열 검사
    if next_queen in queen:
        return #이미 있으면 안됨

    # 대각선 검사
    for queen_row,queen_column in enumerate(queen):
        if abs(len(queen) - queen_row) == abs(next_queen - queen_column): #대각선에 존재
            return

    queen.append(next_queen) #대각선에 없으면 queen에 추가, 다음 진행

    if len(queen)==N:
        answer += 1
        return

    #가지치기
    for n in range(N): # 열기준
        dfs(queen[:],n) #깊은 복사를 통해 list가 재사용되지 않게 한다.

for n in range(N):
    queen = []
    dfs(queen,n) #0행에 들어갈 열들 지정 #0열,1열,2열...n-1열까지 돌면서 경우의 수 확인

print(answer)

얻어가는 것

• 파이썬의 깊은 복사
  • 파이썬에서는 mutable한 값들의 경우 얕은 복사가 되므로 , 리스트를 별도로 관리하려면 별도의 깊은 복사를 수행해주어야 한다.

  • #---immutable---#
    bool,int,float,str
    tuple
    #---mutable---#
    list
    set
    dict
    

  • 깊은 복사 → 리스트 슬라이싱

    dfs(queen[:],n) #전달받은 queen객체를 deep-copy하여 한 루트에서 별도로 관리하도록 한다. 
    ​

• TypeError: unhashable type: 'list' 오류
  • dictionary의 key로 mutable한 것들은 사용 불가하다.
  • 따라서 list를 key로 사용하려 한다면 튜플로 변경해서 넘겨주어야 한다.

  dic = dict()
  dic[[1,2,3]] = True #오류 발생
  
  dic[(**1,2,3)**] = True #리스트를 튜플로 변환하여 key로 사용한다. 
  

느낀점

"211008"

소요 시간 : 3-4H

• 왜 지금까지 dfs 사용했을 때 리스트 값들이 변경되었는지 이유를 알게 되었다.
• 깊은 복사! 필수!