133. Clone Graph

leetcode.com/problems/clone-graph/

Clone Graph - LeetCode

그래프를 클론하는 문제다.

 

dfs로 접근했다.

top to bottom으로 뻗어나갔다가 바텀 찍고 돌아오면서 자식 노드를 생성과 동시에 리턴하면서 부모로 모으는 식으로 하려 했는데

중복 체크에 있어서 애매한 부분이 있어

top to bottom으로 나가되 노드를 미리 생성하고 빈 껍데기라도 미리 리스팅 해서 부모에 추가하는 식으로.. 접근해보았다.

 

32 ms, faster than 93.08% 

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node is None:
            return None
        
        cache = dict()
        
        def cloneAfterScanGraph(root, cloned_root):
            
            cache[root] = cloned_root
            
            cloned_neighbors = []
            
            for neighbor in root.neighbors:
                if neighbor in cache:
                    cloned_neighbor = cache[neighbor]
                else:
                    cloned_neighbor = Node(val=neighbor.val)
                    cloneAfterScanGraph(neighbor, cloned_neighbor)
                cloned_neighbors.append(cloned_neighbor)
            
            cloned_root.neighbors = cloned_neighbors
            
            return cloned_root 
        
        cloned_root = Node(val=node.val)
        root = cloneAfterScanGraph(node, cloned_root)
        
        return cloned_root 

28ms이라고 나와있는데 36ms 답안

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""


# DFS
class Solution:
    def __init__(self):
        self.visited = {}

    def cloneGraph(self, node: "Node") -> "Node":
        if not node:
            return node

        visited = {}

        queue = deque([node])

        visited[node] = Node(node.val, [])

        while queue:
            cur_node = queue.popleft()
            for n in cur_node.neighbors:
                if n not in visited:
                    visited[n] = Node(n.val, [])
                    queue.append(n)
                visited[cur_node].neighbors.append(visited[n])

        return visited[node]