[leetCode 133] Clone Graph (JAVA)

1.문제

Clone Graph - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

 

2.문제설명

 

- 주어진 그래프 구조를 deep Copy 해서 반환 하라는 문제이다.

- Graph 구조로 이루어진 Node 들 중에 하나가 입력으로 들어온다

- Graph 구조를 deep Copy 한 이후 드어온 입력된 노드 로 deep copy 해서 반환 한다.

 

 

-주어진 node 값

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

 

3.소스코드

 

public class Solution {
    private Map<Node, Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }

        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        Node deepCopy = new Node(node.val, new ArrayList<>());
        visited.put(node, deepCopy);

        for (Node neighbor : node.neighbors) {
            deepCopy.neighbors.add(cloneGraph(neighbor));
        }

        return deepCopy;
    }
}

 

4.소스코드해설

 

처음 입력으로 주어진 node 가 null 인지 여부 를 체크!

 

Map 구조로 Visited 라는 방문 맵을 만들고 이미 방문한 정점 일 경우 해당 정점의 복제본을 반환하게 구현 이렇게 하면 그래프 내에서 동일한 정점을 다시 복제 하지 않는다.

 

node 의 deepcopy본을 생성하고 visited 맵에 매핑

 

node 의 이웃 노드들을 순회하면서 각 이웃 노드의 deepcopy를 생성하고 복제된 노드의 이웃 리스트에 추가하면서 재귀적으로 이웃 노드를 붙여준다.

 

이런식으로 DFS 구조로 그래프 node의 복제본을 만들어 deepCopy Graph를 반환한다.

 

 

5.회고

이 코드는 단순 주어진 그래프를 DFS 를 사용하여 그래프를 복사 하는 문제였다 . 그래프의 시간 복잡도는 O(V+E) 노드와 간선 만 순회하면 되기때문에 빠를것이라고 생각 했다. 만약 방문배열을 잡지 않고 순회를 한다면 방문 로직이 없어 무한 루프를 돌거나 O(N^2) 을 돌것이라고 예상 된다.

 

또한 공간 복잡도는 visited HashMap 자료구조로 잡고 있기 때문에 최악의 경우 모든 노드와 그 카피노드가 포함되는 경우 모든 간선의 O(V) 라고 생각하며 재귀적 (DFS)를 사용하므로 스택에 대한 공간복잡도는 그만큼 비례되어 O(N)일것이라고 생각한다.

 

따라서 내가 만든 이 코드는 O(V+E) 시간복잡도 , O(V) 공간 복잡도를 가진다.