leetcode.com 133. Clone Graph

 

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

파이썬 소스: https://bit.ly/4chEDU6

주어진 그래프를 동일하게 한 개 만들어서 리턴하는 문제입니다.

하지만, 메서드에 인자로 주어지는 것은 node 1개 입니다. 따라서, 이 노드에서부터 시작해서, 다른 노드를 찾아 가면서 동일한 그래프를 만들어야 합니다.

그러면 Example 1과 같은 그래프가 주어지고, 노드 1번에서 시작한다고 가정해 보겠습니다.

첫 시작은 1 -> 2 로 갑니다.

그 다음은 1 -> 4 로 갈 수 밖에 없습니다.

첫 1번 노드가 가지고 있는 노드를 BFS로 방문하고 있기 때문입니다.

여기서, 2 -> 3 번으로 갈 때 와, 4 -> 3번으로 갈 때, 3번을 2번 방문하게 됩니다.

즉, edge가 연결된 것에 따라서, 노드에 중복된 방문이 생기기 때문에, 노드를 자료구조에 저장해두고, 노드 번호를 인자로 주어, 노드를 받아오는 것이 구현하기 쉬운 방법입니다.

nodes_clone = {}   if node.val not in nodes_clone.keys():     nodes_clone[node.val] = Node(node.val)

 

nodes_clone변수를 딕셔너리 타입으로 선언하고, 방문하려고 하는 node.val가 key에 들어있지 않으면, 딕셔너리에 저장하는 방식으로 노드를 탐색해 나갈 수 있습니다.

 

BFS 방식으로 노드를 탐색하려면, 큐로 사용할 리스트가 하나 필요합니다. 처음으로 방문할 복사할 노드는 인자로 주어진 node: Optional[‘Node’] 를 사용합니다.

queue = [] if node is not None:     queue.append(node) while queue:     node = queue.pop(0)

queue.pop(0)으로 큐에서 하나씩 노드를 꺼내면서 방문을 시작합니다.

 

방문할 노드가 정해지면, 기존에 방문해서 이미 복사한 노드인지 확인합니다. 원본 노드와, 복사한 노드의 val 값은 같기 때문에, keys()에 val값이 있는지를 확인해서, 노드가 중복해서 복사되는것을 막을 수 있습니다.

if node.val not in nodes_clone.keys():     nodes_clone[node.val] = Node(node.val)

 

복사한 노드를 results(모든 복사가 끝난 뒤에 리턴할 리스트)에 넣어 줍니다. Visitied는 neighbor를 통해서 이웃 노드를 방문할 때, 중복된 복사를 방지하는 역할을 합니다.

node_clone = nodes_clone[node.val] results.append(node_clone) visited.append(node.val)

 

이제 이웃 노드 리스트를 neighbors_clone 변수에 복사할 차례입니다.

neighbors_clone = [] for neighbor in node.neighbors:     if neighbor.val not in visited:         queue.append(neighbor)     if neighbor.val not in nodes_clone.keys():         nodes_clone[neighbor.val] = Node(neighbor.val)     neighbors_clone.append(nodes_clone[neighbor.val]) node_clone.neighbors = neighbors_clone

 

For 루프를 사용해서, 이웃한 노드를 하나씩 꺼내서, 이미 방문하지 않았다면, 방문하기 위해서 queue에 하나씩 넣어 줍니다.

이웃한 노드가 아직 복사되지 않았으면 복사한뒤에, nodes_clone에 넣어줍니다.

neighbors_clone에 복사된 노드를 하나씩 넣어주고, 복사한 node_clone의 neighbors에 복사한 이웃 노드 리스트를 넣어줍으로서, 1개의 노드가 완전히 복사가 끝났습니다.

위와같이 모든 노드들을 방문해서 노드들을 복사하면, 그래프 전체를 복사한 값이 results 변수에 저장됩니다.

 

from typing import Optional # 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: Optional['Node']) -> Optional['Node']:         results = []         nodes_clone = {}         visited = []         queue = []         if node is not None:             queue.append(node)         while queue:             node = queue.pop(0)             if node.val not in nodes_clone.keys():                 nodes_clone[node.val] = Node(node.val)             node_clone = nodes_clone[node.val]             results.append(node_clone)             visited.append(node.val)             neighbors_clone = []             for neighbor in node.neighbors:                 if neighbor.val not in visited:                     queue.append(neighbor)                 if neighbor.val not in nodes_clone.keys():                     nodes_clone[neighbor.val] = Node(neighbor.val)                 neighbors_clone.append(nodes_clone[neighbor.val])             node_clone.neighbors = neighbors_clone         return results[0] if len(results) else None

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul