[leetcode] 133. Clone Graph 파이썬 코드

undirected graph: 방향성이 없는 그래프. (goes both way)

 

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

 

class Node(object):
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        input: Node[]
        output: Node[]
        """
        
        oldToNew = {} # hash map

        def dfs(node): 
            if node in oldToNew: # already exist, return copy
                return oldToNew[node]
            
            # 없으면 copy (new node)를 만들자 
            copy = Node(node.val)
            oldToNew[node] = copy

            for neighbor in node.neighbors:
                copy.neighbors.append(dfs(neighbor))

            return copy
        
        return dfs(node) if node else None

 

 

코드 참고

https://neetcode.io/problems/clone-graph