LeetCode [ 133 | Python ] Clone Graph

문제

https://leetcode.com/problems/clone-graph/description/?envType=study-plan-v2&envId=top-interview-150

주어진 그래프를 복사해야하는 문제.

풀이

아래 시도에서 겪은 고초들을 토대로 새로 작성한 코드.
내가 생각했던 가장 이상적인 형태(첫 노드 생성 -> 이전 노드에 삽입 -> 이전 노드에 삽입 -> …)
로 구현할 수 있었다.

visited에 본래 객체를 키 값으로, 클론 객체를 값으로 저장하는 것을 쉽게 떠올리지 못해서 고민스러웠던 문제였다.

순회 방법은 DFS를 택했는데, 그 이유는 계층적인 구조를 타고 들어가야 한다고 생각했다. (예전에도 언급했듯 계층에서 작업해야 하는 일은 BFS가 더 적절하다는 것을 코드 대부분을 작성하고 깨달았다.)

1. 노드가 비어있는 경우가 있다. 이를 먼저 걸러준다.
2. 방문 체크 딕셔너리를 정의한다.
   딕셔너리인 이유는, 탐색하는 대상이 정수와 배열이 아니므로 그 그 크기를 짐작할 수 없기 때문이다.
3. 재귀를 수행하기 위한 DFS함수를 구현한다.
   1. 가장 먼저 클론 객체를 만든다.
   2. 방문 체크와 동시에 클론 객체를 쉽게 불러오기 위해 값으로 방문체크 딕셔너리에 저장해둔다.
   3. 현재 탐색하는 node의 neighbors를 순회하며 clone객체의 neighbors에 저장한다.
   4. 만약 이미 방문한 노드라면 node의 클론 객체를 return 한다.
   5. 모든 재귀를 마치고 clone을 반환한다.
4. dfs 내부 함수를 호출한다.

class Solution(object):
    
    def cloneGraph(self, node):
        if not node:
            return node
        
        visited = {}
        
        def dfs(node):
            if node in visited:
                return visited[node]
            
            clone = Node(node.val, [])
            visited[node] = clone
            
            for neighbor in node.neighbors:
                clone.neighbors.append(dfs(neighbor))
            
            return clone
        
        return dfs(node)  

시도 1

재귀 형태로 clone 변수에 저장되어있는 루트 노드에 이웃 노드들을 삽입하려 했다.
순회는 쉽게할 수 있었는데 Node 클래스를 따로 관계로 이어줘야한다고 생각하니 쉽지 않았다.

또한 참조 관계를 문제로 재귀의 끝에사 clone을 출력하면 잘 출력됐지만 값을 막상 확인하면 제대로 저장되어 있지 않았다.
추가적으로 방문 체크 배열을 굳이 val 값으로 한 점이 비효율 적이었다.

물론 객체를 직접 저장하지 않으려고 의도하긴 했지만, 근거 없는 의도였다.

class Solution(object):
    def cloneGraph(self, node):
        v = {}
        
        def search(neighbors, clone):
            
            visited = [0] * len(neighbors)

            if not clone.val in v:
                v[clone.val] = visited

            for i in range(len(neighbors)):
                clone.neighbors.append(Node(neighbors[i].val, [clone]))
                if not v[clone.val][i]:
                    v[clone.val][i] = 1
                    search(neighbors[i].neighbors, Node(neighbors[i].val, []))
            
        if node:
            clone = Node(node.val, [])
            res = search(node.neighbors, clone)
                
            return clone
        
        return node  
        

생각 & 정리

재귀를 이용하게 되면 항상 파이썬의 익숙치 않은 참조관계가 걸림돌이 된다.
이론적으로는 어느정도 정리가 된 개념이지만, 역시 실전에서 생각하며 사용하는 것과는 크게 차이가 나는 것 같다.

또한 분명 계층적으로 클론하며 수행되어야 할 작업이 BFS가 아닌 DFS를 먼저 떠올렸다.
첫 단추를 잘못 끼면 이전에 채웠던 단추를 모두 풀어야하는 것 처럼, 첫 솔루션을 선택하는 것은 중요한 것임을 깨달았다.

항상 생각하고, 이유를 되짚어봐야겠다.