백준 9663 N-Queen

백준 9663 N-Queen문제이다.

 

전에 올린 백준 1799 비숍 문제와 유사하지만 조금 더 쉽다.

사용하는 방법은 백트래킹이다.

 

가로, 세로 한 줄에는 하나의 퀸 밖에 들어가지 못하니 한 줄을 기준으로 정하고 하나씩 더해주면 된다.(물론 불가능한 경우는 백트래킹으로 걸러주어야 한다.)

 

여기서는 가로로 한 줄씩 더해주었다.

이 문제에서 조금 귀찮은 부분은 대각선으로 불가능한 경우를 찾아서 제거해주는 것인데, abs(row[x]-row[i]) == abs(x - i)로 찾아주면 된다. (가로, 세로의 차이가 같다면 대각선에 있다)

 

최종코드는 

n = int(input())

ans = 0
row = [0] * n


def is_possible(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
            return False

    return True


def n_queens(x):
    global ans
    if x == n:
        ans += 1
        return

    else:
        for i in range(n):
            # [x, i]에 퀸을 놓겠다.
            row[x] = i
            if is_possible(x):
                n_queens(x + 1)


n_queens(0)
print(ans)

아쉽지만 pypy3로 제출할 수 있도록 하자.