문제 링크: https://leetcode.com/problems/clone-graph/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)
난이도: medium
문제:
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node { public int val; public List<Node> neighbors; }Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Example 1:
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).
Example 2:
Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:
Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
Constraints:
The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.
전략:
그래프의 시작위치 노드가 주어지면 해당 노드부터 탐색하고, 다시 인접한 순서대로 노드를 반환하면 되는 문제이다.
동일한 노드 사이에 중복으로 존재하거나 자기 자신과 연결되는 간선은 없다.
노드를 반환할 때는 원본 객체를 참조하는 것이 아니라, 해당 노드의 정보를 가진 새로운 객체를 생성해 줘야한다.
-> 먼저 모든 그래프의 정점을 순회하며 노드 객체를 교체하고, 다시 새로운 시작 노드를 리턴해준다. 아무래도 깊은 복사가 필요할 듯 하다.
의사코드
class Solution {
public Node cloneGraph(Node node) {
if (시작 노드가 없으면) {
return 빈 노드 그대로 리턴 (null);
}
방문 체크용 List와 큐 선언
Queue q;
List visited;
while (아직 방문 하지 않은 정점 있으면(큐가 비어있지 않으면)) {
다음 정점 방문
정점 객체 저장
if (이전에 방문하지 않은 정점이면) {
큐에 다음 정점 추가
}
}
for (저장한 복사된 정점 객체들) {
정점.neighbors = List<Node> 새로운 정점 객체를 참조하는 리스트;
}
return 복사한 시작 정점 리턴;
}
}
코드 구현:
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
public Node cloneGraph(Node node) {
if (node == null) { return node; }
if (node.neighbors.isEmpty()) { return copyOf(node); }
ArrayList<Node> visited = new ArrayList<Node>();
ArrayList<Node> newNodes = new ArrayList<Node>();
Queue<Node> q = new ArrayDeque<Node>();
Node startNode = node;
q.offer(node);
while (!q.isEmpty()) {
Node vertex = q.poll();
if (!visited.contains(vertex)) {
for (Node adj : vertex.neighbors) {
q.offer(adj);
}
visited.add(vertex);
}
}
for (Node n : visited) {
newNodes.add(copyOf(n));
}
for (Node n : newNodes) {
if (n.val == 1) {
startNode = n;
}
List<Node> newAdjs = new ArrayList<Node>();
for (Node adj : n.neighbors) {
for (Node n2 : newNodes) {
if (adj.val==n2.val) {
newAdjs.add(n2);
break;
}
}
}
n.neighbors = newAdjs;
}
return startNode;
}
public Node copyOf(Node origin) {
Node result = new Node(origin.val);
result.neighbors.addAll(origin.neighbors);
return result;
// return new Node(origin.val, new ArrayList().addAll(origin.neighbors));
}
}
Time: 32 ms (6.68%), Space: 41.7 MB (70.81%) - LeetHub실행결과:
https://github.com/1-vL/LeetCode/blob/main/0133-clone-graph/0133-clone-graph.java
개선 방안:
역시 3중 for문에 ArrayList 3개를 썼더니 시간 복잡도와 공간복잡도가 별로 잘 안 나온 것 같다.
이 문제에서는 1인덱스 기준으로 정점 node의 val이 정해지며, 최대 100개의 정점이 있을 수 있다고 했으므로 이를 활용하여 배열로 랜덤 액세스가 가능하도록 수정해 보면 더 빠른 속도가 가능할 것 같다.
class Solution {
public Node cloneGraph(Node node) {
if (node == null) { return node; }
if (node.neighbors.isEmpty()) { return copyOf(node); }
Node[] visited = new Node[101];
Queue<Node> q = new ArrayDeque<Node>();
Node startNode = node;
q.offer(node);
while (!q.isEmpty()) {
Node vertex = q.poll();
if (visited[vertex.val] == null) {
for (Node adj : vertex.neighbors) {
q.offer(adj);
}
visited[vertex.val] = vertex;
}
}
for (Node n : visited) {
if (n != null) {
visited[n.val] = copyOf(n);
}
}
for (Node n : visited) {
if (n == null) {
continue;
}
if (n.val == 1) {
startNode = n;
}
List<Node> newAdjs = new ArrayList<Node>();
for (Node adj : n.neighbors) {
newAdjs.add(visited[adj.val]);
}
n.neighbors = newAdjs;
}
return startNode;
}
public Node copyOf(Node origin) {
Node result = new Node(origin.val);
result.neighbors.addAll(origin.neighbors);
return result;
// return new Node(origin.val, new ArrayList().addAll(origin.neighbors));
}
}
Time: 26 ms (64.46%), Space: 41.9 MB (47.35%) - LeetHubSolutions 탭의 타인 코드:
class Solution {
public HashMap<Integer, Node> map = new HashMap<>();
public Node cloneGraph(Node node) {
return clone(node);
}
public Node clone(Node node) {
if (node == null) return null;
if (map.containsKey(node.val))
return map.get(node.val);
Node newNode = new Node(node.val, new ArrayList<Node>());
map.put(newNode.val, newNode);
for (Node neighbor : node.neighbors)
newNode.neighbors.add(clone(neighbor));
return newNode;
}
}
Time: 26 ms (64.46%), Space: 42.1 MB (34.6%) - LeetHub회고:
중간에
Node with value 2 was not copied but a reference to the original one.라는 에러를 정말 지겹게 봤었다.
깊은 복사를 한번 하는 건 그렇다 쳐도 정점을 순회하며 그래프 단위로 해야 한다는 점이 골치 아팠던 문제였었다.
clone 메서드를 만들고 재귀적으로 호출하여 그래프를 알아서 순회하도록 하는 방식은 정말 깔끔한 것 같다.
