# 133 Clone Graph

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

문제 조건

• 노드의 수는 [0, 100]이다.
• 1 <= Node.val <= 100
• Node.val은 node마다 유니크한 값을 가지고 있다.
• 자기자신을 반복해서 참조하는 노드는 없다.
• 그래프의 노드는 모두 연결되어 있고 시작 노드에서 접근할 수 있다.
• 그래프를 입력받으면 새로운 노드로 복사하면 된다.

문제 해결

문제 해결 로직

해당 문제는 그래프 탐색만으로 해결할 수 있다. 탐색 중인 노드의 값을 새로운 노드에 해당 값으로 생성하여 연결하면 된다

데이터 입력

• visited HashMap<Integer, Node>로 방문한 노드를 나타낸다. 각 노드 값은 unique이기 때문에 key로 노드 값을 사용한다.
• stack 앞으로 방문할 노드를 저장해둘 Stack이다.
• clone 복사할 노드의 시작 위치 노드이다
• current stack에서 꺼내온 탐색할 노드이다.
• newNeighbor 현재 노드의 이웃 노드 중 스택에 없는 노드이다.

DFS 탐색

• DFS 탐색이란 깊이 우선 탐색으로 시작 노드에서 깊게 노드를 탐색하다 더이상 탐색할 노드가 없으면 이전 노드로 가 계속하는 방식으로 작동한다.
• 방문했던 노드를 방문하지 않기 위해 방문했던 정점을 저장해둘 필요가 있다.
• 방문한 정점을 저장하는 방법에는 1. 방문했던 정점을 전역변수로 관리, 2. 모든 노드가 방문 여부를 저장하는 방법으로 관리가 있는데 나는 전역변수로 관리하였다.
• 스택과 셋으로 탐색을 진행하는 로직은 다음과 같다.

1. 초기 값을 받을 노드 생성.
2. 스택에 해당 노드의 이웃 push
3. 스택이 빌 때 까지 다음 과정 반복
   3-1. 탐색을 시작할 노드를 스택에서 pop하여 받아온다.
   3-2. 해당 노드의 이웃 노드를 탐색한다.
   3-3. 만약 이웃 노드가 방문한 적이 없다면 복사한 현재 노드에 이웃 노드를 만들어 추가하고 방문한 노드에 추가한다.
   3-4. 현재 노드의 복제본에 인접한 노드의 복제본을 연결한다.

Node clone = new Node(node.val);
        visited.put(clone.val, clone);
        stack.push(node);

        while (!stack.isEmpty()) {
            Node current = stack.pop();

            for (Node neighbor : current.neighbors) {
                if (!visited.containsKey(neighbor.val)) {
                    Node newNeighbor = new Node(neighbor.val);
                    visited.put(newNeighbor.val, newNeighbor);
                    stack.push(neighbor);
                }

                visited.get(current.val).neighbors.add(visited.get(neighbor.val));
            }
        }

코드 작성

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

        HashMap<Integer, Node> visited = new HashMap<>();
        Stack<Node> stack = new Stack<>();

        Node clone = new Node(node.val);
        visited.put(clone.val, clone);
        stack.push(node);

        while (!stack.isEmpty()) {
            Node current = stack.pop();

            for (Node neighbor : current.neighbors) {
                if (!visited.containsKey(neighbor.val)) {
                    Node newNeighbor = new Node(neighbor.val);
                    visited.put(newNeighbor.val, newNeighbor);
                    stack.push(neighbor);
                }

                visited.get(current.val).neighbors.add(visited.get(neighbor.val));
            }
        }

        return clone;
    }
}

복잡도 계산

• 시간 복잡도

  • BFS 알고리즘을 수행하면 모든 노드를 한번씩 방문하므로, 시간 복잡도는O(노드의 수+간선의 수)이다.

• 공간 복잡도

  • visited, stack, clone은 각각 노드만큼 사용하기 때문에 공간 복잡도는 O(노드의 수)이다.

회고

• 다음과 같은 점수를 기록했다.
  

• 다른 사람들의 코드 예시를 보았을 때는 재귀적으로 해당 문제를 해결할 수 있었다.
• 방문 기록으로 visited만 사용할 수 있다.
• 만약 이미 방문한 노드면 현재 노드를 반환한다.
• 방문한 노드가 아니라면 vistied에 현재 노드를 넣고 현재의 이웃 노드들에 해당 함수를 재귀적으로 실행하면 된다.

class Solution {
    private HashMap<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 clone = new Node(node.val, new ArrayList<>());
        visited.put(clone.val, clone);

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

        return clone;
    }
}