Clone Graph

https://leetcode.com/problems/clone-graph/

그래프를 복사하는 문제. 결국은 모든 노드를 방문하므로, 이미 가본 곳만 가지 않도록 주의한다.

"""
# Definition for a Node.
class Node:
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        visited = {}
        
        return self.__cloneGraph( node, visited )
    
    
    def __cloneGraph( self, node, visited ):
        if node.val in visited:
            return visited[ node.val ]
        
        clonedNeighborNodes = []
        clonedNode = Node( node.val, clonedNeighborNodes )
        
        visited[ node.val ] = clonedNode
        
        if not node.neighbors:
            return clonedNode
        
        for neighborNode in node.neighbors:
            clonedNeighborNode = self.__cloneGraph( neighborNode, visited )
            clonedNeighborNodes.append( clonedNeighborNode )
                
        return clonedNode