SWEA: 2806 N-Queen

문제

SW Expert Academy

 

문제 풀이

 `DFS`를 통한 백트래킹으로 NxN 크기의 체스판에서 Queen을 배치할 수 있는 경우의 수를 계산할 수 있다. 이는 앞서 다룬 백준: 9663 N-Queen과 동일한 로직으로 풀면 된다. N의 크기가 최대 10이기 때문에 백준의 문제와는 달리 Python으로도 충분히 통과할 수 있다.

 

 다시 한번 로직을 상기해보자면 다음과 같다.

• 행의 경우 DFS를 호출하며 증가시키므로, 별도의 중복확인이 필요하지 않다.
• 열의 경우 해당 열을 선택하면 `set`에 추가하여 중복을 확인한다. 
• 우측 상단에서 좌측 하단의 대각선의 경우 현재 `X + Y`를 `set`에 추가하여 방지할 수 있다.
• 좌측 상단에서 우측 하단의 대각선의 경우 현재 `X - Y`를 `set`에 추가하여 방지할 수 있다.
• 백트랙킹이 가능하도록 가지를 뻗은 후에 `set`에서 다시 `remove`하여야 한다.

 

코드

T = int(input())


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)


for test_case in range(1, T + 1):
    answer = 0
    n = int(input())
    columns, l_diagonals, r_diagonals = set(), set(), set()
    dfs(0)
    print('#' + str(test_case), answer)