Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] N-Queen

[N-Queen]

• 백트래킹을 몰랐던 나도 들어봤을 정도로 정말 잘 알려진 백트래킹 문제이다. 아무래도 혼자 공부할 땐 공부하고싶은 부분들부터 공부하다보니(DFS; 깊이 우선 공부 😅) 다른 부분들에는 언젠가 해야겠다~고 미뤄두고 있었다.
• 문제를 처음 읽고 쭉 고민해 봤는데, 어떤 식으로 흘러가야할지 아이디어는 있었지만 여러 경우에 대해 반복적으로 어떻게 진행시켜야할지 막막했다. 재귀가 쓰여야겠다 싶긴 했는데 영 감이 오질 않았다. 그래도 다른 사람 답 보고 풀긴 싫어서 일단 백트래킹이 뭔지부터 알아야겠다는 생각이 들어서, BFS를 처음 공부할 때 큰 도움을 받았던 BarkingDog 채널에 들어갔다…!!
• [바킹독의 실전 알고리즘] 0x0C강 - 백트래킹의 일부를 들었다. 잘 알려진 문제답게 영상의 연습문제에 N-Queen도 실려 있었다.
  • 또 괜히 풀이 먼저 보긴 싫어서 알고리즘 설명까지 듣고, 첫 번째 연습 문제인 N과 M부터 풀어봤다. 진짜 신기했던 게, 어제 문제였던 소수 찾기에서 itertools를 이용하지 않고 구현해봐야겠다고 생각했던 permutations 문제였다.
  • 뚝딱뚝딱 구현해 보았고 부족한 코드였지만 일단 통과됐다. 설명을 듣고, 더 빠르게 통과된 코드들을 보며 개선해 나갔고, 다시 어제 문제로 돌아가 직접 순열을 생성해서 풀었는데 정말 뿌듯했다!
  • N과 M 시리즈 4개(순열, 조합, 중복순열, 중복조합)를 풀고, 이 문제로 다시 돌아왔다. 여전히 막막했지만, $N=4$일 때, $N=5$일 때에 대해 직접 그려보니 아 백트래킹을 이렇게 적용하면 되겠구나 싶었다.
• 대각선을 체크하는 부분에서 몇 번 실수를 했고, 점차 개선해 나가는 데에 꽤 많은 시간을 쏟았다.
  1. 건너뛸 좌표 목록을 지정하기 위해 DFS 코드를 짰는데,
     • 이 경우 매 $y$, $x$에 대해 $\Delta y=\pm1$, $\Delta x = \pm 1$로 좌표를 생성하기 때문에 사실상 모든 좌표에 대해 건너뛸 좌표로 지정하게 되어버린다.
  2. $\Delta y, \Delta x = \pm d \quad \text{for d=1 to n}$으로 지정하여 건너뛸 좌표 집합을 만들어놓는것까진 정말 좋았는데, 이 경우 다른 상태로 이동하기 위해 set에서 discard할 경우 discard 되지 말아야 할 좌표가 discard되어버리는 문제가 발생했다.
     • (칸 $A$, 칸 $B$의 대각선에 위치한 건너뛸 좌표를 생성해 놓은 상태에서, 백트래킹을 위해 칸 $B$에 의해 생성된 좌표들을 discard하는 과정에서 칸 $A$에 의해 생성된 건너뛸 대각선 좌표들이 지워져버리는 문제)
     • 일단 로직상 맞는지 확인하기 위해 리스트로 바꾸고 작은 $N$에 대해 코드를 돌려보니 맞긴 했으나, 아무래도 리스트를 이용하다 보니 굉장히 느렸다.
  3. try-except + remove를 이용하여 해결하려고 했다. 집합에 원소가 없는 상태에서 remove가 실행되면 KeyError가 발생하기 때문에 KeyError가 발생할 때(두 번 이상 삭제될 때) 따로 그 좌표들을 모아놓고 마지막에 다시 집합에 추가시켜주는 방법이다. 또는 if e in set: discard, else: add를 이용할 수도 있겠다.
  4. 3번을 일단 짜봤는데 정답을 출력하지 못했다. 코드를 수정하던 중 $|i-y_n| \text{ (}y_n \in \text{selected)}$, $|j - x_n| \text{ (}x_n \in \text{selected)}$이 같은지만 확인해주면 된다는 생각이 들어서 이 방법으로 코드를 짰고, 아슬아슬하지만 제한시간내에 통과했다.

Solution.

def solution(n):
    # return [1, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200][n]
    i_pass = set()
    j_pass = set()
    selected = set()
    ret = [0]

    def diag_check(i, j):
        for s in selected:
            if abs(i-s[0]) == abs(j-s[1]): return False
        return True

    def check_control(i, j, f):
        if f:
            selected.add((i, j))
            i_pass.add(i)
            j_pass.add(j)
        
        else:
            selected.discard((i, j))
            i_pass.discard(i)
            j_pass.discard(j)

    def _q(k):
        if k == n:
            ret[0] += 1
            return
        for i in range(n):
            if i in i_pass: continue
            for j in range(n):
                if j in j_pass or not diag_check(i, j): continue
                check_control(i, j, True)
                _q(k+1)
                check_control(i, j, False)
            if k < i+1: return

    _q(0)
    return ret[0]

• 좀 더 개선할 여지가 있는 코드다,,, 일단 너무너무 졸려서 오늘은 여기까지…! 내일 개선해보자!!

---