⭐️ LeetCode 알고리즘 풀이 (with Python)

# Clone Graph

[Quetion]

LeetCode 133. Clone Graph

📌 접근법

[문제 이해]

Node로 구성된 Graph를 그대로 반환

말 그대로 그래프를 복사하여 새로 반환하는 문제이다.

그러기 위해서는 노드를 탐색해야 했고, 순회 알고리즘 중 BFS 방법을 사용했다.
코드의 흐름은 다음 그림 같이 구성했다.

💻 구현

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        from collections import deque
        
        if node is None:
            return None
        
        visited = {}
        queue = deque([node])
        visited[node] = Node(node.val)

        while queue:
            curr = queue.popleft()
            for i in curr.neighbors:
                if i not in visited:
                    queue.appendleft(i)
                    visited[i] = Node(i.val)
                visited[curr].neighbors.append(visited[i])
        return visited[node]

Runtime: 40ms | Memory: 16.65MB
LeetCode 코드 중 Runtime 85%, Memory 89% 해당하는 결과

queue에 값이 존재한다면 queue에서 pop한 값을 현재 노드로 지정하고, 현재 노드의 인접한 값으로 반복하는데 visited에 인접 값이 없다면 queue에 push하고 visited에도 값을 키로 하여 노드를 저장한다.

그리고 visited에서 현재 노드를 키 값으로 하는 인접 값의 리스트에 방문한 노드를 추가하고 이를 queue가 빌 때 까지 반복하게 된다.

📝 Clone Graph 회고

• deque() 모듈을 활용하여 queue를 사용했고, 탐색한 노드를 저장하기 위해 visited라는 해쉬테이블을 활용했다.

• 시간복잡도는 정점의 개수인 V, 간선의 개수 E라 했을 때, O(V + E)를 가진다.

• 다른 솔루션에서도 같은 방법으로 많이 푼 것 같고, 현재 더 이상 개선할 것은 없다고 생각된다.

• 한 가지 간과했던 점은 node가 없을 경우 None을 return해줘야 visited[node] 부분에서 오류가 발생하지 않을거라는 점이다. 그 점을 빼먹고 다시 한번 고민해보다가 실수한 것을 깨닫게 되었다.