백준 9663. N-Queen 문제

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

전체 코드

class Solution:
    def __init__(self, n):
        self.n = n
        self.ans = 0
        self.row = [0] * n

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

        return True

    def n_queens(self, x):
        if x == self.n:
            self.ans += 1
            return

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

        return self.ans


# --- submit ---
n = int(input())
print(Solution(n).n_queens(0))

 

풀이

y축으로 순회를 진행한다. row[x] = y 는 x, y좌표에 queen을 둔다는 의미이다.

for y in range(self.n):
    self.row[x] = y

현재 x 값(=0)으로 is_promising(0)을 호출한다.  is_promising 함수는 0~x-1, x 축을 기준으로 순회하며 체크를 진행한다. 현재 x는 0이므로 순회를 하지 않고 return True를 진행한다.

def is_promising(self, x):
	# x=0, range(0~-1) -> pass 
    for i in range(x):
        if self.row[x] == self.row[i] or abs(self.row[x] - self.row[i]) == abs(x - i):
            return False
    # True 반환
    return True

is_promising이 True이므로 x + 1 진행 후 n_queen을 호출한다.

if self.is_promising(x):
    self.n_queens(x + 1)

 

다음 n_queen 호출에서 아래 코드의 상태를 그림으로 표현하면 다음과 같다.

for y in range(self.n):
    self.row[x] = y

x=1이므로 is_promising(1)이 호출된다.

def is_promising(self, x):
	#x = 0
    for i in range(x):
    	# i = 0, row[0] = 0, row[1] = 0
        # row[1] == row[0] or abs(row[1] - row[0]) - abs(1 - 0)
        # 0 == 0 or 0 == 1 -> True
        if self.row[x] == self.row[i] or abs(self.row[x] - self.row[i]) == abs(x - i):
            return False

    return True

row[x] == row[i]는 row축에 퀸이 존재하는지 확인하는 구문이다. 퀸이 존재하므로 이 경우는 False를 반환한다.

다음으로 y=1인 경우 다음과 같이 row[1] = 1로 설정된다.

 

is_promising은 다음과 같이 처리된다.

def is_promising(self, x):
    for i in range(x):
    	# x=1, i=0, row[1]=1, row[0]=0
        # row[1] == row[0] or abs(row[1] - row[0]) == abs(1 - 0)
        # 1 == 0 or 1 == 1 -> True
        if self.row[x] == self.row[i] or abs(self.row[x] - self.row[i]) == abs(x - i):
            return False

    return True

abs(row[x] - row[i]) == abs(x - i) 는 대각선에 퀸이 존재하는지 확인하는 구문이다. 순회 중인 i를 기준으로 가로 축 차이 abs(x-i), 세로축 차이 abs(row[x] - row[i])가 같으면 대각선에 퀸이 위치한다고 볼 수 있다.

다음과 같이 row[x] < row[i]인 경우를 처리하기 위해 결과를 abs로 처리한다.

i는 for i in range(x)로 항상 i<x 이므로 사실 abs(x-i)는 할 필요가 없다

 

이제 x=1, y=2인 경우를 살펴보자.

is_promising은 다음과 같이 같은 같은 행, 대각선에 위치하지 않으므로 return True를 반환한다.

def is_promising(self, x):
    for i in range(x):
    	# x=1, i=0, row[1]=2, row[0]=0
        # row[1] == row[0] or abs(row[1] - row[0]) == abs(1 - 0)
        # 2 == 0 or 2 == 1 -> False
        if self.row[x] == self.row[i] or abs(self.row[x] - self.row[i]) == abs(x - i):
            return False

    return True

n_queen(x+1)로 하여 n_queen(2)을 진행한다. 

다음 조건을 통해 x == n 이 될 때 성공 케이스 개수를 추가한 후 백트래킹 한다.

def n_queens(self, x):
    if x == self.n:
        self.ans += 1
        return

 

 

결론

왼쪽부터 오른쪽으로 퀸을 순차적으로 넣는다. 각 row[0]는 퀸이 x축 0일 때 y축의 몇번째에 위치하는지 가져온다는 의미이다. 현재 퀸 위치를 x, y로 설정했을 때 x축은 0~x-1, y축은 0~n-1씩 순회하여 (x-1) * n의 위치에서 배치된 퀸과 행, 대각선이 겹치지 않는 곳을 찾아서 퀸을 재귀적으로 배치한다.

퀸의 개수가 n이면 성공 케이스로 추가한 후 백트래킹한다.