[BOJ] #9663 - N-Queen

9663번: N-Queen

 

 

** 문제 유형

• 백트래킹

 

** 풀이

1. 대표적인 백트래킹(Backtracking) 문제
   • N의 크기가 작기 때문에 완전 탐색 가능
2. N x N 크기의 체스 보드 위에 퀸 N개를 서로 공격할 수 없게 배치시켜야 함
3. DFS를 이용하여 간단히 백트래킹 알고리즘을 구현할 수 있음
4. 각 행을 차례대로 확인하면서, 각 열에 퀸을 놓는 경우를 고려함
   • 이 때 위쪽 행과 대각선 행을 모두 확인하며, 현재 위치에 놓을 수 있는지 확인함
5. PyPy3로 제출

 

# x번째 행에 놓은 Queen에 대해서 검증
def check(x):
    # 이전 행에서 놓았던 모든 Queen들을 확인
    for i in range(x):
        # 위쪽 혹은 대각선을 확인
        if row[x] == row[i]:
            return False
        if abs(row[x] - row[i]) == x - i:
            return False

    return True

---

# x번째 행에 대하여 처리
def dfs(x):
    global result
    if x == n:
        result += 1
    else:
        # x번째 행의 각 열에 Queen을 둔다고 가정
        for i in range(n):
            row[x] = i

            # 해당 위치에 Queen을 두어도 괜찮은 경우
            if check(x):
                # 다음 행으로 넘어가기
                dfs(x + 1)

---

n = int(input())

row = [0] * n
result = 0

dfs(0)

print(result)