[Python] N-Queen 9663

---

배경

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

9663번: N-Queen

 

 

코드

def attack(x):
    for i in range(x):
        if row[x]==row[i]:
            return True
        if abs(row[x]-row[i]) == abs(x-i):
            return True
    return False

def dfs(start):
    global cnt
    if start==n:
        cnt +=1
    else:
        for i in range(n):
            row[start] = i
            if not attack(start):
                dfs(start+1)

n = int(input())
row = [0]*n
cnt = 0
dfs(0)
print(cnt)

 

 

설명

백트래킹 방식으로 가지를 뻗어서 되는지 안되는지 모두 확인하는 방법입니다.

핵심은 row를 통해서 열과 행을 체크해주는 것입니다. 퀸은 같은 열, 같은 행이면 안되기 떄문에 row[start]를 통해서 한 행에 하나의 퀸 만을 배치해주고 열 값을 넣어 attack 함수에서 같은 열이 있는지 체크합니다!

그 뒤 대각선 방향의 방향을 체크하면 되는데 대각선은 행과 열의 차이가 같으면 대각선의 방향이므로

abs(row[x]-row[i]) == abs(x-i)를 통해 체크해면 됩니다.

 

 

배운 점

같은 대각선의 좌표를 구하는 방식에 대해 배웠습니다.

그리고 이중 list를 사용하지 않고 구현할 수 있는 방법을 배웠습니다