수련일기(260322): backtrack 조진날

요새는 하루에 하나씩 문제를 푸는 것이 쉽잖다. 야근도 많고 애들도 아프고 집안일도 많다. 고민도 많아서 뭔가 글을 쓰면서 정리를 하려고 한다. 내 맘을 붙들려는 것이다.
매일 여러 영역의 문제를 하나씩 풀면서 소감을 기록하면 리뷰하기도 좋을 것 같아 적어본다. 처가에 와서 양해를 구하고 문제를 풀었다. 스스로 풀려니 정말 기억이 안난다.

N-queens

N-queens라는 문제가 있다. 백트래킹의 거의 전형인데, leetcode hard로, 체스판 변의 길이 n 을 주면, `.Q..` 식으로, 각 줄마다 Q를 규칙에 맞게 1개씩 놓은 것을 표시한 스트링 n 개의 리스트를 묶어 돌려줘야 하는 문제다. 규칙이란, Queen들을 대각선과 + 방향으로 겹치게 놓으면 안된다는 것.
맨 윗 줄부터 채우기로 했다. .Q.. 처럼 놓으면 그 다음 줄은 Q... 이렇게 하고, 결국 row number == n 이면 그때까지의 판을 정답 포맷으로 변환해 돌려주는것이 base case다. 그 전에는 각 줄(row) number로 주어진 입력에 대해 컬럼만 바꿔서 Q를 놓고, backtrack(row + 1) 보낸 다음, Q를 다시 원복, 그리고 다음 column 이런 식으로 모든 옵션에 대해 경로를 표시해서 다음 줄로 보내는 것이다. 포맷이 저런 식이라 나는 [Q, ., ., .] 이런 식으로 row를 다루기 쉬운 array로 구성해, 이들을 붙여서 상태로 갖고 있다가 base case에 이르면 이를 string으로 join 하는 걸로 생각했었다. 하지만 EPI의 솔루션이 위와 같은 경우는 해당 row에 대해 Q가 놓인 column 값을 표시하는 뛰어난 방법을 제시하여, 결국 [Q, ., ., .] := 0 으로 한 줄이 압축되는 걸 보았다. 그렇게 풀어보면..

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        board = [-1] * n
        def backtrack(row):
            if row == n:
                res.append([
                    "." * c + "Q" + "." * (n - c - 1)
                    for c in board])
                return
            for col in range(n):
                if all(
                    abs(c - col) not in (0, row - r)  # 이전의 열(c)과 지금의 열(col)의 차이가 0이라면 같은 열임. 그 차이의 절대값이 row - r 과 같다면 대각선임.
                    for r, c in enumerate(board[:row])  # board는 r=0부터 차례로 기록되어 있음. 따라서 그 인덱스를 r 이라고 생각해도 틀리지 않음
                ):
                    board[row] = col # 숫자를 박는 것만으로 해당 줄의 다른 상태가 원복됨
                    backtrack(row + 1)
        backtrack(0)
        return res

자 이렇게 풀고 나니까 백트래킹 또 풀면 머리에 쥐가 날 것 같았다. GPT에 이런 취지로 다음 문제 추천 부탁했더니 그래프로 살짝 비틀어주었다. 내가 약한건 Clone Graph라서, 풀어보기로 함.

Clone graph

그래프를 deep copy 하는 문제다. 그래프의 노드들은 양방향으로 연결되어 있고, 여기 속한 node가 주어지면, 복제된 그래프의 한 노드를 돌려주는 것이다. 이 경우 해시맵을 사용해서 복제된 노드들을 담으면서, 기존의 그래프에서 DFS or BFS를 하여 노드들을 모두 순회하는 방식으로 진행한다. 여기서 해시맵 사용이 킥인데, 이는 방문여부 및 복제된 노드를 모두 캐싱하는데 사용된다.

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        cloned_map = {}

        def dfs(v):
            if not v:
                return None
            if v in cloned_map:
                return cloned_map[v]

            clone = Node(v.val)
            cloned_map[v] = clone

            for nei in v.neighbors:
                clone.neighbors.append(dfs(nei))

            return clone

        return dfs(node)

요걸 stack overflow가 안날 BFS로 짜면,

from collections import deque

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return None

        cloned_map = {node: Node(node.val)}
        q = deque([node])

        while q:
            v = q.popleft()

            for nei in v.neighbors:
                if nei not in cloned_map:
                    cloned_map[nei] = Node(nei.val)
                    q.append(nei)

                cloned_map[v].neighbors.append(cloned_map[nei])

        return cloned_map[node]