파비의 매일매일 공부기록

2023.04.08 Today's Challenge 본문

Problem Solving/LeetCode

2023.04.08 Today's Challenge

fabichoi 2023. 4. 8. 23:45

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

 

Clone Graph - LeetCode

Can you solve this real interview question? Clone Graph - Given a reference of a node in a connected [https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Connected_graph] undirected graph. Return a deep copy [https://en.wikipedia.org/wiki/Object_copy

leetcode.com

BFS와 hash map 활용

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return node
        
        q, clones = deque([node]), {node.val: Node(node.val, [])}
        while q:
            cur = q.popleft()
            cur_clone = clones[cur.val]

            for ngbr in cur.neighbors:
                if ngbr.val not in clones:
                    clones[ngbr.val] = Node(ngbr.val, [])
                    q.append(ngbr)
                
                cur_clone.neighbors.append(clones[ngbr.val])
        
        return clones[node.val]
반응형

'Problem Solving > LeetCode' 카테고리의 다른 글

2023.04.10 Today's Challenge  (0) 2023.04.10
2023.04.09 Today's Challenge  (0) 2023.04.09
2023.04.07 Today's Challenge  (0) 2023.04.07
2023.04.06 Today's Challenge  (0) 2023.04.06
2023.04.05 Today's Challenge  (0) 2023.04.05
'Problem Solving/LeetCode' Related Articles more
Comments