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

문제 )

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

9663번: N-Queen

 

[ 설명 ]

N개의 Queen을 서로 상대를 공격하지 않도록 NxN 체스판에 위치 시키는 문제 
→ 상대를 공격하지 않으려면 같은 행,열,대각선 상에 위치하면 안된다

 

예를들어 4 Queen의 경우 ,

첫번째 queen을 (1,1)에 둔다면 2번째 queen은 노란색으로 표시한 자리에는 올 수 없다. 

 

[ 풀이 ]

Backtracking Algorithm으로 풀 수 있는 대표적인 문제다. 

 

- Backtracking Algorithm 이란? 

✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법
✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 
     유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다

 

- Node가 Promising한지 점검하는 법 

queen들이 같은 행,열, 대각선에 위치하면 안된다. 
✔ 대각선에 위치하는 경우 : |queen1의 행 - queen2의 행| = |queen1의 열 - queen2의 열|이 된다

 

 

- Backtracking Algorithm으로 형성되는 State space tree

 

 

< Nqueens Function의 Algorithm >

✔ column으로만 이루어진 list → stack
✔ queen들이 서로 공격하지 않고 배치되는 경우의 수 →  count 
✔ 현재 접근하는 행 & 몇번째 queen인지 의미 → x (0부터 시작)

If  4번째 queen까지 다 배치한 경우 
        1. count를 1개 늘려준다
Else 
        1. x번째 queen의 열에 접근해서 → i (0~N-1)  
                  Ⅰ. 열의 값을 하나씩 늘려준다
                  Ⅱ.  If x번째 queen의 좌표가 promising하면
                           →  x+1번째 queen에 대해서도 Nqueens fuction수행 

 

< Promising Fuction의 Algorithm >

✔ 현재 접근하는 행 & 몇번째 queen인지 의미 → x 

 

1. 전의 queen들에 모두 접근한다  → i (0~x-1)
          If 열이 겹치거나 대각선이 겹치면 
                   → False 
2. 열이 겹치거나 대각선이 겹치는 queen이 없는 경우에 True

 

★ python3로 제출하면 시간 초과가 된다,, 구글링해보니 백트래킹의 대부분 문제들이 python으로 풀가애 부적합하다고 한다..  

- python code (pypy3)

import sys 
input=sys.stdin.readline

# Promising 한지 (대각선, 열)
def promising(x):
    for i in range(x):
        if stack[i]==stack[x] or (x-i)==abs(stack[x]-stack[i]):
            return False
    return True


def Nqueens(x):
    global count 
    if x==N: # 끝까지 다 도달한 경우
        count+=1
    else:
        for i in range(N): # x번째 queen의 열 정하기 
            stack[x]=i 
            #primising한 경우 x+1번째 quuen에 접근 
            if promising(x): 
                Nqueens(x+1)


N=int(input())
stack=[0]*N # initialize the Stack
count=0
Nqueens(0)
print(count)