[백준] 9663번 N-Queen By Python

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

두 가지 방법이 있을 것 같았다.
1. N x N 배열을 만들고 다 순회하면서 경우의 수를 찾는 브루스포스
2. DFS를 이용한 재귀방법

N개의 퀸이 놓이기 위해서는 각 열과 각 행에 퀸이 하나씩 존재해야 한다.

퀸은 가로, 세로, 대각선을 모두 차단하기 때문에 한 행에 1개가 놓이면 다른 퀸은 놓일 수 없는데 n행이니 n개의 퀸이 놓일 수 있고 이는 열에도 똑같은 해당사항이다.

그렇다면 첫행에 대해서만 퀸을 배치하고 재귀적으로 같은 열과 대각선에 퀸이 존재하는지 검사하면 여차저차되지 않을까?
행렬에서 대각선 상의 퀸이 놓였음을 어떻게 알 수 있을까?

퀸의 대각선은 기울기가 1인 일차함수처럼 생각할 수 있다.
내가 퀸을 놓은 곳을 (i,j)라고 하고 그 퀸이 갈 수 있는 곳을 (x,y)라고 할 때 기울기가 1이기 때문에 (y-j)/(x-i) = 1이다.
이는 y-j = x-i 라고 할 수 있는데 기울기가 -1 이어도 똑같은 퀸의 대각선 경로라고 볼 수 있으니 절대값을 붙이면 좋을 것이다.```

abs(x - i) == abs(row[x] - row[i])

퀸의 위치 유효성 검사 함수

def isPossible(x):
    for i in range(n):
        ## 현재 참고하는 row[x]의 i열에 퀸을 뒀는데 모든 행의 i열에 퀸이 있는지 검사한다. 있으면 세로가 겹치니까 False
        ## 대각선으로 중첩되는지 검사한다.
        if row[x] == row[i] or \
                abs(x - i) == abs(row[x] - row[i]):
            return False
    return True

재귀 함수

def Queen(x):
    global count
    if x == n:
        count += 1
    for i in range(n):
        ## 현재 행 위치에서 퀸을 놓은 열
        row[x] = i
        if isPossible(x):
            Queen(x+1)

최종 결과

n = int(input())
count = 0
row = [0] * n

def isPossible(x):
    for i in range(x):
        ## 현재 참고하는 row[x]의 i열에 퀸을 뒀는데 모든 행의 i열에 퀸이 있는지 검사한다. 있으면 세로가 겹치니까 False
        ## 대각선으로 중첩되는지 검사한다.
        if row[x] == row[i] or \
                abs(x - i) == abs(row[x] - row[i]):
            return False
    return True


def Queen(x):
    global count
    if x == n:
        count += 1
        return

    for i in range(n):
        ## 현재 행 위치에서 퀸을 놓은 열
        row[x] = i
        if isPossible(x):
            Queen(x+1)

Queen(0)
print(count)

사실 대각선을 어떻게 검사할지 생각이 안나서 다른 블로그 좀 참고했다.
대각선이 왜 x- i, row[x]-row[i] 인지 잘 이해 안가서 그건 내가 일차방정식의 기울기로 표현했는데 맞았길 바란다. 오랜만에 중학수학 꺼내서 기분 좋았다.

이차행렬이 아니라 일차행렬로 표현한것도 다른 블로그에서 참고했다.
이부분은 하단의 블로그에서 이해하면 좋다.

https://seongonion.tistory.com/103