133. Clone Graph (Hash Table, Depth-First Search, Breadth-First Search, Graph)

링크 - https://leetcode.com/problems/clone-graph/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

Graph문제이므로 BFS와 DFS로 풀 수 있다.

1) BFS

우리는 hash table를 사용한 방법을 이용할 것이다. hash table의 key는 old node를 담고 value에는 new node를 담을 것이다. 그래서 매번 새로운 노드를 탐색할때마다 새로운 node를 만들어서 pair를 만들고, neighbors또한 각 old node에서 neighbor를 for문으로 돌때 업데이트 할 것이다.

"""
# 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 []
"""

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return node

        visited = {}
        queue = deque()
        queue.append(node)
        visited[node] = Node(node.val, [])

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

        return visited[node]

Time Complexity: O(n+m) 여기서 n은 node의 개수이고, m은 edge의 개수이다.

Space Complexity: O(n) 우리는 visited이라는 hash table를 사용하기 때문에 최대 n개의 node개 저장된다.

2) DFS

"""
# 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 []
"""

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return node

        visited = {}

        def dfs(node):
            if node in visited:
                return

            visited[node] = Node(node.val, [])
            for neighbor in node.neighbors:
                if neighbor not in visited:
                    dfs(neighbor)
                visited[node].neighbors.append(visited[neighbor])

        dfs(node)
        return visited[node]

Time Complexity: O(n+m) 여기서 n은 node의 개수이고, m은 edge의 개수이다.

Space Complexity: O(n) 우리는 visited이라는 hash table를 사용하기 때문에 최대 n개의 node개 저장된다.