[Graph 문제] LEETCODE.133 Clone Graph

문제풀이

이번 문제는 전형적인 DFS/BFS 문제 유형이다. 해당 문제 해결에 대한 아이디어는 아래와 같다.
1. nodes는 input의 각 노드와 그 복사본을 매핑하는 딕셔너리입니다.
2. stack은 BFS를 사용하여 그래프를 탐색하는 데 사용되는 스택입니다.
3. stack이 빌 때까지 먼저 추가된 노드를 추출하고 해당 노드와 연결된 노드들을 추가로 탐색해나간다.
4. neighbor.val이 nodes에 없으면 stack에 추가되고 copy() 함수를 사용하여 복사하고 기존 노드에 연결시킨다
5. stack이 모두 빈 경우 모두 탐색이 완료되었기 떄문에 ans를 return하면 정답이 된다.

from collections import deque
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        def copy(node):
            if node is None:
                return
            return Node(node.val)
        
        if not node:
            return node
        
        ans=copy(node)
        nodes={node.val:ans}
        stack = deque()
        stack.append(node)
        
        while stack:
            #edge = stack.pop()->DFS/popleft인 경우 BFS
            edge = stack.popleft()
            curr = nodes[edge.val]
            for neighbor in edge.neighbors:
                if neighbor.val not in nodes:
                    stack.append(neighbor)
                    nodes[neighbor.val]=copy(neighbor)
                #(참조->이 경우 답이 안됨) curr.neighbors.append(copy(neighbor))    
                curr.neighbors.append( nodes[neighbor.val])        
        return ans

           
           

Lookback

1. 해당 문제에서는 Deep Copy 방식으로 Graph를 복사해나가야 하며 이 때 From/To Edge 정보를 어떻게 관리하여 연결할 것인가가 중요한 부분이다. 해당 문제에 대한 접근을 Dictionary 방식을 통해 해결했다.