[LeetCode] - M - 133. Clone Graph

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

LeetCode - The World's Leading Online Programming Learning Platform

 

🌿 - 설명

주어진 그래프를 깊은 복사하는 것을 구현하면 된다.

 

 

📌- 풀이

간단하게 생각하면 결국 전체를 탐색해서 복사를 해야 한다고 생각해서 BFS 방식으로 풀면 되겠다고 생각을 했음.

 

1. root 노드로부터 시작
2. 반환하게 될 결과값을 담는 map과, 해당 노드들을 BFS하기 위한 인접리스트를 담을 que 초기화
3. que가 빌 때까지 반복
4. 인접리스트들을 계속해서 map에 집어넣으면서 반복

백준과 프로그래머스 같은 곳에서 BFS를 풀이하는 것과 LeetCode에서 Node를 사용해서 BFS를 하는 것이 방식은 같지만 뭔가 더 생각해야 될 것들이 많아서 복잡한 것 같음.

 

 

🔥 - Java 코드

/*
// 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<Integer, Node> map = new HashMap<>();
	 Queue<Node> que = new LinkedList<>();
	 map.put(node.val, new Node(node.val));
	 que.add(node);
	 
	 while(!que.isEmpty()) {
		 Node cur = que.poll();
		 Node temp = map.get(cur.val);
		 
		 for(Node neighborsNode: cur.neighbors) {
			 if(!map.containsKey(neighborsNode.val)) {
				 map.put(neighborsNode.val, new Node(neighborsNode.val));
				 que.add(neighborsNode);
			 }
			 temp.neighbors.add(map.get(neighborsNode.val));
		 }
	 }
     
     return map.get(node.val);
    }
 
 
}