leetcode medium : Clone Graph (Grind 75 Graph 문제 3)

예전에 풀어본 문제다.

근데 또 실수했다.

이 문제는 지금 카피되어 결과물로 나오고 있는 그래프를 어떻게 관리할거냐가 핵심인데

각 노드의 값이 유니크하다는 점을 이용해 hash map을 이용하면 된다.

그럼 source graph에서 어떤 노드가 주어지면 그 값을 이용해 대응되는 destination graph의 값을 찾을 수 있다.

 

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return None
        q, nodemap = deque([node]), {node.val : Node(node.val)}
        while q:
            src = q.popleft()
            for n in src.neighbors:
                if n.val not in nodemap:
                    nodemap[n.val] = Node(n.val)
                    q.append(n)
                nodemap[src.val].neighbors.append(nodemap[n.val])
        return nodemap[node.val]

 

복잡도는

시간 : O(N)

공간 : O(N) (한 노드에 다른 모든 노드가 붙어있는 경우 큐가 N에 비례해서 찬다.)