[백준 9663] N-Queen (Python) / G4

문제

9663.N-Queen

코드

n = int(input())

res = 0
row = [0] * n

def is_promising(x):
    for i in range(x):
        # 같은 줄에 있거나
        # 대각선 상에 있으면 False
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
            return False
    return True

def n_queens(x):
    global res
    if x == n:
        res += 1
        return
    else:
        for i in range(n):
            row[x] = i
            if is_promising(x):
                n_queens(x+1)

n_queens(0)
print(res)

코드 설명

row[i] = j = 퀸을 [i,j]에 놓는다는 의미
퀸 위치를 정한 후 is_promising함수를 통해 놓을 수 있는 위치인지 판단하였다.

퀸을 놓지 못하는 경우는
1. 같은 줄에 하나라도 퀸이 있거나
2. 대각선에 퀸이 있다면
그 위치는 놓지 못하는 곳이므로 False를 return 해주었다.

• row라는 리스트에 저장되어있는 값 중 하나라도 현재 줄에 있는 값과 같다면 같은 줄에 있다는 의미
• 대각선 판단은,

  • 예를 들어 (3,3)을 판단한다고 가정하자
    왼쪽 대각선의 좌표는 (2,2), (1,1)이다. 즉, x좌표끼리 뺀 값과 y좌표끼리 뺀 값이 같아야 한다.
    오른쪽 대각선의 좌표는 (2,4), (1,5)이다. 이 또한 x좌표끼리 뺀 값과 y좌표끼리 뺀 값이 같아야 한다.

    이 규칙을 코드로 작성하면 abs(row[x] - row[i]) == abs(x - i)로 판단할 수 있게 된다.

n_queen 함수에서는 for문을 통해 queen을 놓을 수 있는 모든 위치를 다 찾아서 판단후 재귀를 통해 만약 해당 위치에 퀸을 놓을 수 있다면 다음 줄을 탐색해서 또 새로운 위치를 찾는 식으로 구현하였다.
이렇게 모든 경우를 다 탐색하다보니 시간복잡도가 올라가서 위 코드를 python으로 제출하면 시간초과가 나지만 pypy로 제출했을 경우 정답처리가 되었다.

코드 참고

https://seongonion.tistory.com/103