[LeetCode/Java] 133. Clone Graph

0. 문제

https://leetcode.com/problems/clone-graph/?envType=study-plan-v2&envId=top-interview-150

1. 문제 설명

• 무방향 그래프의 참조가 주어질 때 해당 그래프를 복사하라.

2. 문제 풀이

2.1. 접근법

• BFS를 활용해서 인접한 노드 중 방문하지 않은 노드들을 추가한다.

3. 코드

/*
// 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 null;
	 
	 Map<Node, Node> map = new HashMap<>();
	 Queue<Node> q = new LinkedList<>();
	 map.put(node, new Node(node.val));
	 q.add(node);
	 
	 while(!q.isEmpty()) {
		 Node currNode = q.poll();
		 Node cloneNode = map.get(currNode);
		 
		 for(Node adjNode: currNode.neighbors) {
			 if(!map.containsKey(adjNode)) {
				 map.put(adjNode, new Node(adjNode.val));
				 q.add(adjNode);
			 }
			 cloneNode.neighbors.add(map.get(adjNode));
		 }
	 }
     
     return map.get(node);
 }
}

4. 결과

5. 개선점

5.1. 시간 복잡도 개선

• 방문했던 노드들을 체크하면서 이미 방문한 노드는 건너띄면 시간 복잡도를 개선할 수 있다.

/*
// 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 null;
   
       Node visited[] = new Node[101]; 
       
       Node copiedNode = new Node(node.val);

       
       Queue<Node> q = new LinkedList<>();
       q.add(node);

       visited[copiedNode.val] = copiedNode;

       while(!q.isEmpty()){

           Node popOrig = q.poll();
           
           for(Node n:popOrig.neighbors){
               if(visited[n.val] == null){
                   visited[n.val] = new Node(n.val);
                   q.add(n);
               }
               visited[popOrig.val].neighbors.add(visited[n.val]);
               
           }
       }

       return copiedNode;

       
   }
}

• 결과