[ Top Interview 150 ] 133. Clone Graph

문제

133. Clone Graph

 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.

• Input : Graph 구조로 이루어진 Node들 중에서 하나의 Node

• Ouput : Graph 구조를 deep copy 한 후에, Input으로 제공된 Node의 deep copy를 반환

• 제공된 코드

  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;
      }
  }

알고리즘 전략

• 기본 전략

  • 각 노드 별로 deep copy를 실시하기
  • 기본적으로 재귀를 이용해서 노드 자신과 연결된 Node를 복사한다. (DFS 형식의 탐색)

• 연결된 Node 복사 전략

  • 이미 한 번 복사된 Node는 또 다시 복사를 하면 안된다. ()
  • 그래서 Map<Node, Node> oldToNew를 이용하여 복사한 Node는 Map에 넣고, 이미 복사된 Node가 있는지 확인할 수 있다.

답안 1

• Time complexity : $O(n^2)$
• Space complexity : $O(n)$

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        
        return cloneGraph(node, new HashMap<>());
    }

    private Node cloneGraph(Node node, Map<Node, Node> oldToNew) {
        if (oldToNew.get(node) != null) {
            return oldToNew.get(node);
        }

        Node cloneNode = new Node(node.val);
        oldToNew.put(node, cloneNode);
        for (Node neighbor : node.neighbors) {
            Node cloneNeighbor = oldToNew.getOrDefault(neighbor, cloneGraph(neighbor, oldToNew));
            cloneNode.neighbors.add(cloneNeighbor);
        }
        return cloneNode;
    }
}