[백준]9663 - N 퀸즈 문제 풀이(파이썬,Python)

문제

9663번: N-Queen

 

들어가며

대각선에 대해 많은 고민을 하다가 너무 시간을 많이 쓰다 못 푼 문제였다.

백트래킹 참 어렵다...

 

 

코드

n = int(input())

ans = 0
row = [0] * n


def is_promising(x):
    for i in range(x):
        if row[x] == row[i] or (row[x] + x == row[i] + 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

    for i in range(n):
        row[x] = i
        if is_promising(x):
            n_queens(x + 1)


n_queens(0)
print(ans)

 

풀이

이 코드에선 row[x] 배열을 만들어 좌표를 표시한다.

row[x] = i

x행의 i열을 의미한다.

 

문제가 원하는 것은 n x n 보드에서 n개의 퀸을 놓는 것이다.

이를 다시 말하면 모든 행엔 최소한 하나의 퀸이 존재해야 한다.

한 행의 모든 열에 다 놓아보면서 그게 이전의 퀸 위치랑 겹치면 그 경우의 수는 제거되는 방식이다.

 

그렇기 때문에 is_promising 메소드가 중요하다.

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

열 비교, 오른쪽 대각선, 왼쪽 대각선 순이다.

대각선을 비교하는 방법은 좌표 값을 잘 관찰하면 찾을 수 있다.

오른쪽 대각선을 먼저 본다면 각각의 좌표 x,y 값의 합이 모두 일치함을 알 수가 있다.

왼쪽 대각선은 각 좌표의 x와 다른 좌표 x, y좌표와 다른 좌표 y 값의 차이가 일정하다는 것을 알 수가 있다.

이를 비교하면 대각선 판별을 할 수 있게 된다.

열 비교는 row 배열 안에 있는 값이 열이기 때문에 이미 있는지 파악이 가능하다.