[백준] 9663번 N-Queen

사용 언어 - PyPy3

9663번: N-Queen (골드4, DFS 백트래킹 문제)

문제 ★백트래킹 문제★

9663번: N-Queen

 

 

정답

DFS 백트래킹 재귀함수 조합 문제 !! (아래 그림 참고)

1.  DFS nqueen()

행(x)이 고정되어 있을 때 열(i)를 하나씩 증가시켜준다. (0,0) -> (0,1) -> (0,2) -> (0,3)

조건을 만족해서 퀸을 두려고 한다면, row[x] = i 로 (x,y)에 퀸의 위치를 저장해야한다. 모든 열에 테스트를 완료했으면, 행을 한개 증가시켜 다시 열을 하나씩 증가시킨다. (1,0) -> (1,1) -> (1,2) -> (1,3)

행(x)와 N이 같아진다면, 즉 총 N개의 퀸을 모두 사용했으면, 경우의 수(ans)를 한개 추가해준다.

 

시작은 (0,0)에서 for문으로 한개씩 늘리는 방식이기 때문에, 

최종적으로 nqueen(0), print(ans) 하면 끝!

 

2. Promising 예외 조건 처리

퀸은 상하좌우, 대각선으로 이동이 가능하기 때문에, 상하좌우, 대각선에 있으면 퀸끼리 서로 공격이 가능하다. 퀸들 서로가 상하좌우, 대각선에 위치하면 안된다.

• row[x] == row[i] 상하좌우 테스트

같은 열에 이미 퀸이 있는 x줄과 퀸을 둬도 되는지 테스트 하는 i줄이 같다. 한 개의 열에 두개의 퀸이 놓여진 것이므로 상하좌우를 테스트할 수 있다.

예) 현재 (0,0)에 퀸을 둔 상태이고, 그 다음 재귀함수로 (1,0)에 퀸을 두고 조건에 맞는지 테스트한다면?

-> row[0] == row[1] == 0 으로, 같은 열의 0번째 줄과 1번째줄 에 퀸이 놓여져 있는 것이라 상하좌우 규칙에 어긋나서 (1,0)에 퀸을 둘 수 없다.

 

• abs(row[x]-row[i]) == abs(x-i) 대각선 테스트

 대각선은 각 행열 값이 (1,1), (2,2), (3,3) 의 형태이다. 각각의 행과 열을 뺐을 때 절댓값이 같을 수 밖에 없는 것을 이용하여 대각선 여부를 테스트할 수 있다.

예) 현재 (0,0)에 퀸을 둔 상태이고, 그 다음 재귀함수로 (1,1)에 퀸을 두고 조건에 맞는지 테스트한다면?

-> row[0] == row[1] 같은 열에 퀸이 놓여있진 않지만,

행과 열을 각각 빼줬을 때 abs(0-1) = abs(0-1) 그 값이 같다면 대각선에 놓여있어서 (1,1)에 퀸을 둘 수 없다.

 

 

import sys
n = int(sys.stdin.readline().rstrip())

ans = 0
row = [0] * n

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

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

n_queens(0)
print(ans)

---

레퍼런스

• 정답 참고

백준 9663번 N-Queen 파이썬 풀이

Python 백준 8320번 - N-Queen, 백트래킹 알고리즘과 pruning(가지치기)

잔재미코딩 온라인 강의 사이트입니다

• 깃허브 정답

GitHub - yyeongeun/codingtest: 코딩테스트 공부