백준: 9663 N-Queen

문제

9663번: N-Queen

 

문제 풀이

 N * N의 체스판이 주어졌을 때, 서로 공격할 수 없도록 퀸을 배치할 수 있는 경우의 수를 찾는 문제이다. 해당 문제의 경우 다음과 같은 경우의 수를 판단하여 백트랙킹을 하면 된다.

 

• 같은 행 또는 열에 다른 퀸이 존재하는가?
  • 행의 경우 DFS를 통해 재귀호출을 하게 되면 하나의 행에 대한 선택을 진행하므로 별도로 확인할 필요는 없다.
  • 열의 경우 예를 들어, 첫번째 퀸의 자리가 (0, 0)이라면 같은 열에 있는지 확인해 주어야 한다.
• 우측 상단에서 좌측 하단(↙)의 대각선에 퀸이 존재하는가?
  • 배치된 퀸의 X + Y를 추가하여 다음에 선택한 퀸의 X + Y와 같다면 ↙에 존재하는 것이다.
• 좌측 상단에서 우측 하단(↘)의 대각선에 퀸이 존재하는가?
  • 배치된 퀸의 X - Y를 추가하여 다음에 선택한 퀸의 X - Y와 같다면 ↘에 존재하는 것이다.

 

코드

from sys import stdin


def dfs(x):
    global answer

    if x == n:
        answer += 1
        return

    for y in range(n):
        if y in columns or (x + y) in l_diagonals or (x - y) in r_diagonals:
            continue
        columns.add(y)
        l_diagonals.add(x + y)
        r_diagonals.add(x - y)
        dfs(x + 1)
        columns.remove(y)
        l_diagonals.remove(x + y)
        r_diagonals.remove(x - y)


if __name__ == '__main__':
    answer = 0
    n = int(stdin.readline())
    columns, l_diagonals, r_diagonals = set(), set(), set()
    dfs(0)
    print(answer)

 `l_diagonals`는 `↙`를 의미하며, `r_diagonals`는 `↘`를 의미한다. 느림보 파이썬으로는 통과할 수 없어 PyPy3를 사용하여야 시간 초 내에 값을 구할 수 있다.