[백준] 9663 파이썬(python) : N-Queen - (★)

9663번 : N-Queen

9663번: N-Queen

 

 

백트래킹을 이용하여 푸는 대표적인 문제 N-Queen이다. 퀸은 상하좌우, 대각선으로 움직일 수 있다는것을 알아야한다. 일반적으로 퀸이 움직이는 곳은 체스판위이기 때문에 2차원 그래프를 생성해줘야 하는 줄 알았지만 1차원 리스트의 인덱스와 리스트 값을 이용해서 퀸의 위치를 지정하는 방법이 있었다.

 

import sys
n = int(sys.stdin.readline())
res = 0
row = [0]*n #1

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

def n_queen(x): #5
    global res
    if x == n: #6
        res += 1
        return
    for i in range(n): #7
        row[x] = i #8
        if is_promising(x): #9
            n_queen(x+1)
n_queen(0)
print(res)

 

#1 : 1차원 배열로 행을 생성. 인덱스는 행, 값은 열이 된다.

#2 : 퀸을 놓을 자리가 가능성이 있는지 판단하는 함수. True or False를 리턴한다

#3 : 현재 깊이까지 반복. 퀸을 맨 위 행부터 차례로 채우고 있으므로 자신의 행 아래는 다른 퀸과의 이동경로가 겹치는지 확인할 필요가 없다.

#4 : #3을 이유로 현재의 위치에서 가능성을 판단할때는 직선은 왼쪽과 위쪽만 겹치지 않는지 확인하면 되고, 대각선은 왼쪽위 대각선과 오른쪽 위 대각선만 이동경로가 겹치지 않는지 확인하면 된다.

row[x] == row[i]는 직선의 이동경로를 판단하고 abs(x-i) == abs(row[x]-row[i])는 대각선의 이동경로를 판단한다.

인덱스는 행, 리스트의 값은 열을 의미하므로 abs(x-i)는 x축 abs(row[x]-row[i])는 y축을 의미한다. 예시로 (3, 3)에 퀸을 넣으려고 함수를 호출했을때 오른쪽 대각선으로 만나는 (1, 5)에 퀸이 존재한다면 abs(2) == abs(-2)를 만족하므로 대각선의 이동반경에 걸리게 된다.

이동반경에 걸린다면 False를 리턴하고 반복문이 끝날때까지 걸리지 않는다면 현재위치에 퀸을 심을 수 있으므로 True를 리턴한다.

#5 : 처음으로 깊이이자 row배열의 첫번째 인덱스 0으로 호출한다. 

#6 : 모든 row리스트를 다 채웠다면(x == n) 경우의 수 +1

#7 : 인덱스 0번부터 n까지 반복을 돌면서 row리스트의 인덱스에 알맞은 값(열)을 채워준다.

#8 : 인수 x를 깊이이자 row리스트의 인덱스로 선택했으므로 백트래킹을 이용해 하나하나 값을 갱신. 반복문의 인덱스로 row[x] = i 로 퀸을 놓을 자리 갱신

#9 : 현재 퀸을 놓을 자리가 적절한 자리인지 판단하는 함수 호출

 

---

1차원 리스트의 인덱스를 이용해 2차원 그래프를 접근하는 문제

14889번 : 스타트와 링크

 

참고한 블로그