[Algorithm][Python] 백준(BOJ) 9663 N-Queen (Gold 4)

[문제]

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

---

🛠 풀이

예전에 풀었었는데, 다시 보니 새삼 새롭다.ㅎㅎ
백트래킹 중에 유명한 문제다.

1. 첫번째 행부터 차례로 퀸을 놓는다.
2. 각 행을 돌면서 이전의 행에 놓여 있는 퀸과 조건이 맞는지 확인한다.
   • 조건에 맞으면 다음 행으로 넘어간다.
   • 조건에 맞지 않으면 이전 행으로 돌아간다.(백트래킹)
     • 조건
       1. 같은 열이 아니여야 한다.
       2. 대각선이 아니여야 한다.
          같은 행인지는 확인할 필요 없음
3. 마지막 행까지 퀸이 놓여지면 결과(경우의 수) +1 을 한다.

❗️ 주의 할 점

• 체스판 배열을 2차원으로 하면 시간 초과가 난다. 1차원 배열로 구현해야 한다. ( arr[row] = col )
• 퀸을 놓아도 될지 검사할 때, 앞 줄(윗 줄)만 확인하면 된다.

[내 코드]

def check(row):
    # 이전 행만 확인
    for preRow in range(row):
        # 같은 열이거나 대각선에 있는지 확인
        if arr[preRow] == arr[row] or abs(arr[preRow]-arr[row]) == abs(preRow-row):
            return False
    return True

def dfs(row):
    global result
    if row == n:
        result += 1
        return

    for column in range(n):
        arr[row] = column
        if check(row):
            dfs(row + 1)


n = int(input())
result = 0
#arr[row] = column
arr = [0] * n

dfs(0)
print(result)