[백준] 9663. N-Queen

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

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

---

접근 방법: DFS

• 퀸이 배치될 수 있는 모든 가짓 수를 구하는 문제인데, 가장 간단하게 구하는 방법은 별 다른 휴리스틱 없이 DFS를 이용해 모든 자리 위에 퀸을 배치해보는 것이다.

import sys

def nQueenPuzzle(n):
    board = [-1] * n
    count = 0

    def isValid(row):
        for i in range(row):
            if board[row] == board[i] or board[row] == board[i] - (row - i) or board[row] == board[i] + (row - i):
                return False
        return True

    def dfs(row):
        nonlocal count
        if row == n:
            count += 1
            return

        for i in range(n):
            board[row] = i
            if isValid(row):
                dfs(row + 1)
        return

    dfs(0)
    return count

print(nQueenPuzzle(int(sys.stdin.readline())))

---

    def isValid(row):
        for i in range(row):
            if board[row] == board[i] or board[row] == board[i] - (row - i) or board[row] == board[i] + (row - i):
                return False
        return True

• 퀸이 p행 q열에 있을 때, p+1행에 퀸이 올 수 없는 자리는 q-1, q, q+1 이다. 이를 확장해나가면 퀸이 p행에 있을 때, 이후에 오는 p+n행에서 퀸이 올 수 없는 자리는 q-n, q, q+n이 된다.

• 이를 이용하여 isValid(row) 라는 함수를 만들어 row 행에 퀸이 배치되었을 때, 배치된 퀸이 row - 1 까지의 행에 배치된 퀸과 충돌하지 않는지를 확인하였다.

---

    def dfs(row):
        nonlocal count
        if row == n:
            count += 1
            return

        for i in range(n):
            board[row] = i
            if isValid(row):
                dfs(row + 1)
        return

• 이 후, dfs(row) 를 돌며 탐색을 하는데, 가장 윗 row 부터 순서대로 퀸을 배치하고, 매 번 퀸을 배치할 때 마다 isValid(row) 를 돌려 배치된 퀸끼리 충돌이 발생하지 않으면 row 를 하나 늘려 dfs(row + 1) 를 불러오는 식으로 재귀적인 방식으로 코드를 작성했다.

• 매개변수로 입력받은 row 가 최초에 입력되었던 N 과 같아질 경우, 모든 row 에 퀸이 충돌없이 배치된 상태이므로 count 를 하나 늘려주고 return 하였다.

---

타임아웃

def isValid(board, row):
    for i, q in enumerate(board[:row]):
        if board[row] == q or board[row] == q - (row - i) or board[row] == q + (row - i):
            return False
    return True

def dfs(board, row, res, n):
    if row > 1 and not isValid(board, row - 1):
        board[row - 1] = -1
        return board, res
    elif row > 1 and row == n:
        res += 1
        board[row - 1] = -1
        return board, res

    for i in range(n):
        board[row] = i
        board, res = dfs(board, row + 1, res, n)

    board[row] = -1
    return board, res

• 최초에 작성했던 dfs() 와 isValid() 는 위와 같았는데, 답은 제대로 구해졌으나 백준에 제출시 타임아웃이 발생하였다.

• 이 후 코드를 최적화하기 위해 isValid() 내부에서 반복문을 돌기 위해 체스판 리스트를 매 번 슬라이싱하는 부분을 단순히 인덱스만 불러와 참조하게 바꾸었다.

• dfs() 에서도 매 번 리턴되기 전에 체스판 리스트의 해당 행을 -1 로 되돌려놓는 방식으로 작성을 했었는데, 필요없다고 생각되어 삭제하였다.

• 마지막으로 코드 가독성을 높이기 위해 dfs() 에 체스판 리스트, 카운트, N값 모두를 매개변수로 주던 것을 nQueenPuzzle() 이라는 전체 함수로 묶어 nonlocal 변수로 불러올 수 있도록 하여 매개변수의 갯수를 줄였다.

• 이렇게 수정한 이후에도 타임아웃이 발생했었는데, 백준에서 코드를 제출할 때 사용하는 언어를 Python3에서 PyPy로 바꾸니 아슬아슬하게 통과되었다.