1. 문제 설명

N-Queen

2. 문제 분석

N X N 위의 좌표 (행, 열)에 퀸이 N개 놓일 수 있다. 이때 퀸이 서로 공격하면 안 되는 경우의 수를 N에 따라 구해야 한다. 즉, 서로 같은 행, 열, 대각선에 퀸이 존재하면 안 된다.

1. row 행에 넣을 퀸의 위치를 정하자. (0 <= row <= n-1)
2. 지금까지 이전 행에 둔 퀸과 열 또는 대각선 방향으로 같다면 놓을 수 없다.
3. 다르다면, 이번 행까지는 서로 공격하지 않는 퀸을 놓을 수 있다는 뜻이다.
4. row+1 행에 넣을 퀸의 위치를 새롭게 정하자. 즉 지금까지 성공했다는 뜻은 row 번까지는 행, 열, 대각선 모두 겹치는 부분이 없다는 것이다.
5. 지금 놓을 행 row가 n과 같다면 주어진 모든 행(최대 n-1)에 놓을 퀸을 다 둔 것이기 때문에 더 고려할 필요가 없다. N-Queen이 가능한 경우이다.
6. 모든 경우의 수를 카운트해 return한다.

• 백트래킹으로 N-Queen이 가능한 좌표 역시 확인할 수 있다. 본 문제에서는 개수만 카운트했다. DFS처럼 백트래킹에서 사용할 수 있는 알고리즘을 유연하게 생각하는 습관을 기르자. DFS는 아는 데 이런 문제에서 헷갈렸다.

3. 나의 풀이

def dfs(queens, row, n):
    if row == n: return 1
    # n-1행까지 모든 퀸을 놓는 데 성공. 즉 n-queens 성공
    total = 0
    for col in range(n):
        queens[row] = col
        # (row, col)에 퀸을 놓는다.
        queenable = True
        # 지금까지 놓은 퀸과 행에서는 겹치지 않는다.
        for i in range(row):
            if queens[i] == queens[row] or abs(queens[i]-queens[row]) == abs(row - i):
                # 지금까지 놓은 퀸 중 열 또는 대각선에서 겹친다.
                # N X N이므로 이등변. 대각선으로 놓인 퀸이 있다면 이 두 퀸의 각 행과 열의 차는 같기 때문.
                queenable = False
                break
        if queenable:
            # 지금 행 row까지 퀸을 놓을 수 있다면 다음 행에 놓을 퀸을 찾자.
            total += dfs(queens, row+1, n)
            # 퀸을 끝까지 놓을 수 있는 경우만 total에 더해진다.
    return total

def solution(n):
    queens = [0]*n
    # queens[row] = col을 통해 (row, col)에 퀸이 들어 있음을 확인하자
    total = dfs(queens, 0, n)
    return total

``