LeetCode 133번: Clone Graph(JAVA)
문제출처 133번: Clone Graph
❔ 문제
무방향 연결 그래프의 val=1 인 Node가 주어졌을 때, 이 무방향 연결 그래프의 Clone(deepcopy)을 구성하여 복사된 val=1인 Node를 반환하는 문제.
⏩ 예시
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]] Explanation : There are 4 nodes in the graph.
1st node (val = 1)’s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)’s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)’s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)’s neighbors are 1st node (val = 1) and 3rd node (val = 3).
❕ 문제풀이
import java.util.*;
class Solution {
Map<Integer, Node> visited = new HashMap<>(); // 방문한 노드의 val과 복사된 해당 노드를 저장하는 Map
public Node cloneGraph(Node node) {
if(node == null) return null; // 1.
return dfs(node);
}
public Node dfs(Node node){ // 2.
Node newNode = new Node(node.val); // 3.
visited.put(node.val, newNode); // 4.
for(Node neighbor : node.neighbors){ // 5.
if(!visited.containsKey(neighbor.val)){ // 6.
newNode.neighbors.add(dfs(neighbor)); // 7.
}else{
newNode.neighbors.add(visited.get(neighbor.val));
}
}
return newNode;
}
}
- 간선이 없다면 그대로 null을 반환한다.
- DFS 알고리즘으로 기존 그래프를 탐색한다.
- 현재 Node를 복제하되, Neighbor는 비어있다.
- 현재 Node의 값을 방문처리하고, 복제된 Node를 Map에 같이 삽입한다.
- 현재 Node의 Neighbor를 순회한다.
- Neighbor가 방문하지 않은 Node(val)라면 Neighbor를 매개변수로 dfs를 호출하고 반환값을 복제된 노드의 Neighbor에 추가한다.
- Neighbor가 방문한 Node(val)라면 visited의 val을 통해 복제된 Node를 Neighbor에 추가한다.
💯 고찰
Solution 코드들은 풀이는 대부분 BFS, DFS, for문으로 풀이를 했다. 다만 Memory와 Runtime의 차이는 분기처리, Map의 사용 등으로 나뉜것으로 보인다.
1ms, 0.2MB 정도의 크지 않은 차이지만 여러 풀이를 보며 새로운 방식들을 접한 경험이 되었다.
