Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Medium 133. Clone Graph

tags: leetcode

問題

イデア

「無向グラフの deepcopy を作成し、返せ」という問題です。

BFS、DFSで実装出来ると思いますが、今回はBFSで実装します。

解法

Queueを使います。つまりBFSです。

  • 与えられた nodequeue に格納します。
  • 今まで通ったオリジナルのノードのコピーを格納する連想配列 copy_of_original を作成します。
  • そして、 queue の中身が空でなければ以下を実行します。
    • curqueue の先頭のノードで、このノードの neighbors を全て調べます。
      • もし、 copy_of_original に入っていなければ、その neighborcopy_neighbor として neighbor と結びつけます。そして、グラフの更新をし、最後に neighbor をキューに追加します。
      • もし、既に入っていれば、 その cur のコピーを作り、 neighborに対応するコピーをその neighbors に追加します。

計算量

ノードの数を $N$ とします。

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • $O(N)$

Python

"""
# 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 
        copy_node = Node(node.val, [])
        copy_of_original = {node: copy_node}
        queue = collections.deque([node])
        while queue:
            cur = queue.popleft()
            for neighbor in cur.neighbors:
                if neighbor not in copy_of_original: # neighbor is not visited
                    copy_neighbor = Node(neighbor.val, [])
                    copy_of_original[neighbor] = copy_neighbor
                    copy_of_original[cur].neighbors.append(copy_neighbor)
                    queue.append(neighbor)
                else:
                    copy_of_original[cur].neighbors.append(copy_of_original[neighbor])
        return copy_node