https://programmers.co.kr/learn/courses/30/lessons/12952

---

1. 전체 코드

def solution(n):
    answer = [0]
    def dfs(idx, queens):
        if idx == n:
            answer[0] += 1
            return
        for col in range(n):
            # 중복 column 체크
            if col in queens:
                continue
            # 중복 diagonal 체크
            diagonal_flag = False
            for row, queen in enumerate(queens):
                count = idx - row
                if col == queen - count or col == queen + count:
                    diagonal_flag = True
                    break
            if not diagonal_flag:
                dfs(idx + 1, queens + [col])
    dfs(0, [])
    return answer[0]

---

2. 후기

문제를 보고 DFS와 백 트래킹을 바로 떠올릴 줄 알아야 한다.

---

2-1. 코드 설명

1. def dfs(idx, queens):
   idx는 행의 인덱스를 의미하며 queens는 0번째 행부터 순서대로 퀸이 위치한 열을 저장하는 리스트이다. 아래 그림은 queens = [1, 3, 0, 2] 이다.
   

2. answer = [0]:
   답을 값을 저장할 수 있는 타입인 리스트로 선언했다. 만약 answer = 0 으로 했다면 중첩 함수 안에서 answer += 1 계산은 수행 될 수 없을 것이다.

3. # 중복 diagonal 체크:

# 현재 2행에 놓을 수 있는 퀸의 열을 찾고 있는 상태라고 가정한다. queens[0] = 2
for row(=0), queen(=2) in enumerate(queens):
                count(=2) = idx(=2) - row(=0)
                if col(0열 or 4열) == queen(=2)-count(=2) or col == queen(=2) + count(=2):
                    diagonal_flag = True
                    break
            if not diagonal_flag:
                dfs(idx + 1, queens + [col])

count는 위의 행에 놓여있는 퀸이 대각선 공격이 가능한 열의 위치를 현재 행(=idx) 기준으로 계산할 수 있게 해주는 가중치라고 생각하면 된다.

만약 idx = 1 이라면, count를 통해 빨간색으로 색칠된 부분의 열의 위치를 계산할 수 있을 것이다.