LeetCode : 133. Clone Graph

문제 링크

문제 먼저 읽기

연결된 방향이 없는 그래프에서 노드의 참조가 주어집니다.

깊은 복사를 한 그래프를 반환하세요.

어떻게 풀까?

생각

• 이웃을 순회하면서 재귀로 해결하는 것을 시도해보았습니다.

수도코드

class Solution {
    public Node cloneGraph(Node node) {
        ArrayList<Node> neighbors = new ArrayList<>();
        boolean[] visit = new boolean[101];
        
        for (int i=0; i<node.neighbors.size(); i++) {
            if (!visit[node.neighbors.get(i).val]) {
                Node temp = cloneGraph(node.neighbors.get(i));
                neighbors.add(temp);
                visit[node.neighbors.get(i).val] = true;
            }
        }
        
        Node clonedNode = new Node (node.val, neighbors);
        return clonedNode;
    }
}

• visit이 매번 초기화되기 때문에 의도와 다르게 StackOverflowError 가 발생합니다. 전역변수로 수정하였습니다.
• 전역적으로 Node를 저장해두었다가 연결 관계를 맺어줘야할 필요성이 느껴져 Map 자료구조로 변경하였습니다. 혹은 boolean 배열이 아니라 Node 직렬 배열로 저장해두어도 될 것 같습니다.

class Solution {
    
    private Map<Integer, Node> visited = new HashMap<>();
    
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        
        if (visited.containsKey(node.val)) {
            return visited.get(node.val);
        }
        
        Node clonedNode = new Node(node.val);
        visited.put(node.val, clonedNode);
        
        for (Node neighbor : node.neighbors) {
            clonedNode.neighbors.add(cloneGraph(neighbor));
        }

        return clonedNode;
    }
}

결과

<aside> 💡 Success

Details

Runtime: 25 ms, faster than 95.73% of Java online submissions for Clone Graph.

Memory Usage: 41.9 MB, less than 46.92% of Java online submissions for Clone Graph.

</aside>

다른 풀이 방식과 문제 회고

• sample 24 ms submission
  • Node와 Node 관계를 맵으로 저장하여 푼 사례입니다. 관계 자체를 저장하여 공간 복잡도 효율도 개선하였다는 생각이 듭니다.

class Solution {
    public Node cloneGraph(Node node) {
        
        if(node == null){
            return null;
        }
        
        if (node.neighbors == null) {
            return new Node(node.val);
        }

        Map<Node, Node> map = new HashMap<>();
        
        DFS(node, map);
        
        return map.get(node);
    }
    
    private void DFS(Node node, Map<Node, Node> map){
        
        if(map.containsKey(node)){
            return;
        }
        Node newNode = new Node(node.val);
        map.put(node, newNode);
        for(Node neighbor: node.neighbors){
            
            DFS(neighbor, map);
            newNode.neighbors.add(map.get(neighbor));
        }
    }
}

• sample 41200 KB submission

class Solution {
    public void dfs(Node node, HashMap<Node, Node> dict)
    {
        for (Node nd : node.neighbors) {
            if (!dict.containsKey(nd))
                dict.put(nd, new Node(nd.val));
            dict.get(node).neighbors.add(dict.get(nd));
        }
        for (Node nd : node.neighbors)
        {
            if (dict.get(nd).neighbors.size() == 0)
                dfs(nd, dict);
        }
    }
    public Node cloneGraph(Node node) {
        HashMap<Node, Node> dict = new HashMap<>();
        if (node != null) {
            dict.put(node, new Node(node.val));
            dfs(node, dict);
            return dict.get(node);
        }
        return null;
    }
}