LeetCode 51. N-Queens with Python 백트래킹 문제

https://leetcode.com/problems/n-queens/description/

오호라... 굉장히 어렵게 느껴졌던 문제,,,
솔직히 아이디어 못 떠올려서 리트코드 제출한 사람거 읽었다ㅋㅎㅋ

아이디어는 이렇다
한 행(row)씩 읽어가면서 하나씩 Queen을 둬본다.
이 때 queen을 둔 열(column과 양쪽 대각선 /, \ 둘 다 visited 처리를 한다.)
여기까진 많이 떠올렸을 거 같은데 대체 대각선 처리를 어떻게 하지?? 고민이 있었는데

이런 규칙을 갖고 있었다.
이렇게 방문처리를 해가면서 해가 나오지 않으면 다시 다른 곳에다 둬보는 방식으로 처리하는 전형적인 백트래킹 문제였다. (그리고 어려웠다..ㅎㅎ)

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        state=[["."] * n for _ in range(n)]
        res = []

        # 같은 열에 있는지
        visited_cols = set()
        # 같은 왼쪽 위 - 오른쪽 아래 대각선에 있는지
        visited_diagonals = set()
        # 같은 왼쪽 아래 - 오른쪽 위 대각선에 있는지
        visited_antidiagonals = set()

        def backtrack(r):
            # 행 끝까지 다 훑으면 현재 상황 result에 넣기
            if r==n:
                res.append(["".join(row) for row in state])
                return

            for c in range(n):
                # 왼쪽 위 - 오른쪽 아래 대각선 상
                diff = r - c
                # 왼쪽 아래 - 오른쪽 위 대각선 상
                _sum = r + c

                # 현재 위치가 열도 안겹치고 양쪽 대각선 다 안겹치면 퀸을 놓을 것임
                if not (c in visited_cols or diff in visited_diagonals or _sum in visited_antidiagonals):
                    # 현재 놓은 퀸 컬럼은 방문처리
                    visited_cols.add(c)
                    # 현재 놓은 퀸 양방향 대각선도 방문처리
                    visited_diagonals.add(diff)
                    visited_antidiagonals.add(_sum)
                    # 퀸 놓기
                    state[r][c] = 'Q'
                    # 다음 행으로 넘어가기
                    backtrack(r+1)

                    # r번째 행 0번째 열에도 넣어보고 1번째 열에도 넣어보고 해야함으로 재귀 다 돌면 이전에 넣었던 애들 다 원상 복구
                    visited_cols.remove(c)
                    visited_diagonals.remove(diff)
                    visited_antidiagonals.remove(_sum)
                    state[r][c] = '.'

        # 첫번째 줄부터 훑기
        backtrack(0)
        return res

대충 동작과정을 보자면
bt(0)
r=0, c=0, diff=0, _sum=0
vc=(0), vd=(0), va=(0)
state[0][0]='Q'
bt(1)
r=1, c=0, diff=1, _sum=1
전에 놨던 퀸이랑 같은 열
r=1, c=1, diff=0, _sum=2
전에 놨던 퀸이랑 같은 대각선
r=1, c=2, diff=-1, _sum=3
vc=(0, 2), vd=(0, -1), va=(0, 3)
bt(2)
r=2, c=0, diff=2, _sum=2
전에 놨던 퀸이랑 같은 열
r=2, c=1, diff=1, _sum=3
전에 놨던 퀸이랑 같은 대각선 /
r=2, c=2, diff=0, _sum=4
전에 놨던 퀸이랑 같은 열, 같은 대각선
r=2, c=3, diff=-1, _sum=5
전에 놨던 퀸이랑 같은 대각선
재귀 종료: 다시 r=1, c=2일 때로 돌아옴
backtract(r+1) 후에 있는 코드 실행
c=2, diff=-1, _sum=3 을 각각 방문처리했던 것을 되돌림
그리고 퀸 놓았던 것도 취소
r=1, c=3, diff=-2, _sum=4
vc=(0, 3), vd=(0, -2), va=(0, 4)
bt(2)
.
.
.
이런식으로 r==n, 즉 행 끝까지 다훑으면 해가 맞기 때문에 result에 추가하는 방식이다.
재귀를 정말 잘 이해하고 있고 머릿속으로 그려져야(?) 풀 수 있었던 문제 같다!
굳!