[LeetCode] 133 | Clone Graph | Python

---

문제 링크: https://leetcode.com/problems/clone-graph/

---

문제

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

---

조건

• The number of nodes in the graph is in the range [0, 100].
• 1 <= Node.val <= 100
• Node.val is unique for each node.
• There are no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.

---

내 풀이

deque에 현재 입력으로 들어온 노드를 저장하고, nodes라는 dictionary에 노드를 하나씩 추가할 것이다.

deque에서 맨 앞 노드를 pop해서 그 노드의 neighbor를 탐색한다.

문제 조건에서 모든 노드의 val은 서로 다르다고 가정했으므로, neighbor.val이 nodes에 존재하지않는다면 새로 만듦과 동시에 얘도 나중에 탐색해야하므로 deque에 추가한다.

neighbor를 현재 노드의 neighbor에 추가한다.

이 과정을 반복하면 된다.

---

코드

"""
# 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 not node:    return node
        deq = deque([node])
        nodes = {node.val: Node(node.val)}
        
        while deq:
            poped = deq.popleft()
            cur = nodes[poped.val]
            
            for neigh in poped.neighbors:
                if neigh.val not in nodes:
                    nodes[neigh.val] = Node(neigh.val)
                    deq.append(neigh)
                
                cur.neighbors.append(nodes[neigh.val])
            
        return nodes[node.val]