[leetcode][133] Clone Graph

문제 : leetcode.com/problems/clone-graph/

---

모든 노드들이 연결된 방향성 없는 그래프가 주어진다.

이를 깊은 복사한 트리를 생성한 뒤 반환하라.

---

트리 노드부터 탐색해가면서 노드를 붙여나가는 BFS 방식으로 풀었다.

생성된 노드들에 대한 정보를 저장하기 위한 map 을 추가했다. 해당 map의 key는 node.val이 고유하다고 명시되어 있기 때문에 이를 사용하고 map의 value는 Node*을 저장한다.

 

탐색 중인 노드의 neighbors 들 중 생성되지 않은 노드가 있다면 생성한 뒤 map에 저장, 탐색 중인 노드의 clone 노드에 생성한 노드를 neighbors로 등록. 이미 생성된 노드라면 map에서 해당 노드를 가져온 뒤 clone 노드의 neighbors로 등록하는 식으로 반복해나간다.

 

시간복잡도는 정점의 개수를 V, 간선의 개수를 E라 한다면 O(N+2V). 2V인 이유는 방향성 없는 그래프이기 때문이다.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/133.%20Clone%20Graph.cpp