문제 링크

https://www.acmicpc.net/problem/9663

문제 설명

• 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력

풀이

• 행별로 백트래킹 수행
• 열을 돌면서 해당 열이 가능한 열인지 체크
• 가능할 경우
  • check = True
  • DFS
  • check = False

가능한 열인지 체크

• j열에 퀸이 왔을 경우 cols[j] = True
• i행 j열에 퀸이 왔을 경우 up[i+j] = True
  • up : 기울기가 양수인 대각선 리스트
• i행 j열에 퀸이 왔을 경우 down[i-j+n-1] = True
  • down : 기울기가 음수인 대각선 리스트
    

느낀 점

• 다른 언어에서 되는 풀이가 파이썬에서는 안된다
• 해당 행, 열이 가능한 자리인지 체크하는 부분을 좀 더 효율적으로 짜야 한다

코드

def init():
    n = int(input())
    count = 0
    cols = [False] * n
    up = [False] * (2 * n - 1)
    down = [False] * (2 * n - 1)
    return n, count, cols, up, down
    

def dfs(level):
    global count
    if level == n:
        count += 1
        return
    for j in range(n):
        if possible(level, j):
            cols[j] = up[level + j] = down[level - j + n - 1] = True
            dfs(level + 1)
            cols[j] = up[level + j] = down[level - j + n - 1] = False


def possible(level, j):
    if cols[j] or up[level + j] or down[level - j + n - 1]:
        return False
    return True


n, count, cols, up, down = init()
dfs(0)
print(count)