프로그래머스: N-Queen

문제

코딩테스트 연습 - N-Queen

 

문제 풀이

 앞서 다룬 백준: 9663 N-Queen, SWEA: 2806 N-Queen과 동일한 문제이다. Queen의 경우 상, 하, 좌, 우에 다른 Queen이 없어야 하고, 대각선으로도 Queen이 없어야 한다는 조건을 만족하여야 한다.

 

 따라서 Queen을 배치할 수 있는 경우를 판단하는 것은 다음과 같다.

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

 

코드

answer = 0
columns, l_diagonals, r_diagonals = set(), set(), set()

def dfs(x, n):
    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, n)
        columns.remove(y)
        l_diagonals.remove(x + y)
        r_diagonals.remove(x - y)

def solution(n):
    dfs(0, n)
    return answer