참고
문제해설
NOTE
•
주어진 node를 이용해서 Graph를 복제한 결과를 출력해야 한다.
문제 로직고민
NOTE
// 1. 초기 node 복제, val의 범위는 1~100
Node clone = new Node(node.val);
Node[] nodesClone = new Node[101];
// 2. DFS 탐색 (원본과 복제 node를 둘다 dfs로 돌림)
Stack stack = new Stack();
Stack stackClonde = new Stack();
Set visited = new HashSet();
stack.add(node);
visited.add(node.val, );
while(!stack.isEmpty())
Node cur = stack.pop();
Node curClone = stackClone.pop();
for(Node n : current.neighbors)
if !visited.contains(n.val)
visited.add(n.val);
stack.push(n);
// node가 이미 복제되어있는가를 확
if(cloneNodes[n.val] == null) cloneNodes[n.val] = new Node(n.val);
Node clone = cloneNodes[n.val]
// 무방향 그래프이므로 양쪽 연결
clone.neighbors.add(curClone);
curClone.neighbors.add(clone);
stackClone.push(clone);
// 4. 반환
return clone;
Java
복사
•
모든 그래프의 node를 복제하기 위해선 먼저 탐색이 먼저 진행되어야 한다.
◦
DFS방식을 채택하고, 초기 node를 이용해 복제 node를 생성한다.
◦
이후 탐색하면서 node의 정보들을 이용해 새로운 node를 만들고 연결해준다.
작성코드
NOTE
class Solution {
public Node cloneGraph(Node node) {
if(node == null) return node;
Node[] cloneNodes = new Node[101];
Node cloneNode = new Node(node.val);
cloneNodes[node.val] = cloneNode;
Stack<Node> stack = new Stack();
Stack<Node> stackClone = new Stack();
Set<Integer> visited= new HashSet();
stack.push(node);
stackClone.push(cloneNode);
visited.add(node.val);
while(!stack.isEmpty()){
Node cur = stack.pop();
Node curClone = stackClone.pop();
for(Node n : cur.neighbors){
if(cloneNodes[n.val] == null) cloneNodes[n.val] = new Node(n.val);
Node clone = cloneNodes[n.val];
if(!visited.contains(n.val)){
visited.add(n.val);
stack.push(n);
clone.neighbors.add(curClone);
curClone.neighbors.add(clone);
stackClone.push(clone);
}
}
}
return cloneNode;
}
}
Java
복사
실패
실패 했는데 이유가 무엇일까?
•
현재 방식의 탐색으로는 순환이 있다면 모든 간선을 사용하지 않는다!
◦
1 → 2 → 3 → 4 까지 이루어지고, 4-1 간선이 처리가 안됨
◦
무방향을 처리하기 위해 방문하지 않은 노드지점이 나오면 양쪽으로 추가해주었다.
◦
이 방식말고 각 노드의 모든 간선을 방향이 있다 생각하고 추가하는 방식으로 수정한다.
class Solution {
public Node cloneGraph(Node node) {
if(node == null) return node;
Node[] cloneNodes = new Node[101];
Node cloneNode = new Node(node.val);
cloneNodes[node.val] = cloneNode;
Stack<Node> stack = new Stack();
Stack<Node> stackClone = new Stack();
Set<Integer> visited= new HashSet();
stack.push(node);
stackClone.push(cloneNode);
visited.add(node.val);
while(!stack.isEmpty()){
Node cur = stack.pop();
Node curClone = stackClone.pop();
for(Node n : cur.neighbors){
// 수정한 부분!
if(cloneNodes[n.val] == null) cloneNodes[n.val] = new Node(n.val);
Node clone = cloneNodes[n.val];
clone.neighbors.add(curClone);
if(!visited.contains(n.val)){
visited.add(n.val);
stack.push(n);
stackClone.push(clone);
}
}
}
return cloneNode;
}
}
Java
복사
다른사람 풀이
NOTE
class Solution {
public Node cloneGraph(Node node) {
if (node == null) {
return null;
}
return cloneGraph(node, new HashMap<>());
}
public Node cloneGraph(Node node, Map<Integer, Node> visited) {
if (visited.containsKey(node.val)) {
return visited.get(node.val);
}
ArrayList<Node> newNeighbors = new ArrayList<>();
Node newNode = new Node(node.val, newNeighbors);
visited.put(node.val, newNode);
for (Node neighbor : node.neighbors) {
newNeighbors.add(cloneGraph(neighbor, visited));
}
return newNode;
}
}
Java
복사
실행시간이 빠른 코드
•
DFS방식을 동일하게 사용했는데 보다 효율적인 코드로 작성했다.
class Solution {
public Node cloneGraph(Node node) {
// BFS approach
if(node==null) {
return null;
}
Queue<Node> q = new ArrayDeque<>();
Map<Node, Node> map = new HashMap<>();
q.offer(node);
map.put(node, new Node(node.val));
while(!q.isEmpty()) {
Node u = q.poll();
for(Node v: u.neighbors) {
if(!map.containsKey(v)) {
q.offer(v);
map.put(v, new Node(v.val));
}
map.get(u).neighbors.add(map.get(v));
}
}
return map.get(node);
}
}
Java
복사
•
전체탐색이므로 BFS역시 마찬가지로 사용이 가능하다.