forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhaxr369.java
More file actions
90 lines (76 loc) ยท 2.14 KB
/
haxr369.java
File metadata and controls
90 lines (76 loc) ยท 2.14 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.ArrayList;
import java.util.List;
/**
* Runtime: 25 ms (Beats 72.12%)
* Memory: 44.35 MB (Beats 34.32%)
* Space Complexity: O(N)
* - ๋ชจ๋ ๋
ธ๋ ์ ์ฅ => O(N)
* - visited๋ก ๋ณต์ฌํ๋ ๋
ธ๋ ๊ด๋ฆฌ => O(N)
* > O(N)
* Time Complexity: O(N)
* - ๋ฃจํธ๋
ธ๋๋ถํฐ ๋ชจ๋ ๋
ธ๋๊น์ง ํ๋ฒ์ฉ ํ์ => O(N)
* > O(N)
*
*/
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 == null) {
Node newNode = new Node(node.val, null);
return newNode;
} else if (node.neighbors.isEmpty()) {
Node newNode = new Node(node.val, new ArrayList<>());
return newNode;
}
Node[] visited = new Node[104];
Node ans = new Node(node.val, new ArrayList<>(node.neighbors));
visited[ans.val] = ans;
dfs(ans, visited);
return ans;
}
/**
* node์ ๋ฆฌ์คํธ๋ฅผ dfs๋ก ๋ณ๊ฒฝํด๊ฐ๋ค.
* ๋ค๋ง, ๋ณ๊ฒฝํ๋ ๋
ธ๋๋ ๋ค์ ๋ณ๊ฒฝํ์ง ์์
*/
private void dfs(Node node, Node[] visited) {
List<Node> neighbors = node.neighbors; // ์ด์ ๊ฒ
List<Node> newNeighbors = new ArrayList<>(); // ์ ๊ป์ง
// ํ๋์ฉ ์๊ฑธ๋ก ๋ฐ๊พธ์
for (Node n : neighbors) {
if (visited[n.val] != null) {
newNeighbors.add(visited[n.val]);
continue;
}
Node newN = new Node(n.val, new ArrayList<>(n.neighbors)); // ๊ป์ง ๋ง๋ค๊ธฐ
visited[newN.val] = newN;
dfs(newN, visited); //
newNeighbors.add(newN);
}
node.neighbors = newNeighbors; // ์ ๊ท ๋ฆฌ์คํธ๋ก ๋ฐ๊ฟ์น๊ธฐ
// printNode(node);
}
private void printNode(Node node) {
System.out.print("val -> " + node.val);
System.out.println(" size -> " + node.neighbors.size());
node.neighbors.forEach(n -> System.out.print(n.val));
System.out.print('\n');
}
}