(Graph, Medium) Clone Graph

https://leetcode.com/problems/clone-graph/description/

무방향 그래프 탐색을 하면서 깊은 복사를 하는 문제인 것 같다.
Node 인스턴스를 새로 만들어야 한다는 뜻

DFS, BFS 어떤 방식으로든 탐색이 가능할 것 같다.

BFS 방식
Queue를 이용해서 poll(), 이어지는 노드는 offer() - 큐가 비어있을 때까지 탐색

주의해야 할 점은 무방향이기 때문에 visited 체크를 해주어야 한다는 것

추가로 구현 단계에서 어려웠던 점은 원본과 복사본을 모두 순회해야 한다는 것이다.
아이디어를 떠올리기가 어려웠다.

HashMap을 사용해서 origin / copy 쌍을 다룰 수 있다면 좋겠다고 생각했다.
Node 자체를 key/value로 써도 될 듯 - 기본적으로 해시코드와 equals 모두 다를테니

원본 Node를 기준으로 BFS를 수행하되, 이것을 key로 뽑을 수 있는 copy Node를 만들어 누적해가는 방식으로 한다.
맵의 containsKey를 사용하여 visitied 여부도 체크할 수 있다.

시간복잡도는 O(V + E)다.
V - Vertex
E - Edges

class Solution {

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

        Queue<Node> que = new LinkedList<>();        
        que.offer(node);

        Map<Node, Node> copiedMap = new HashMap<>();
        copiedMap.put(node, new Node(node.val));

        while (!que.isEmpty()) {
            Node current = que.poll();
            Node copied = copiedMap.get(current);

            for (Node n : current.neighbors) {

                if (!copiedMap.containsKey(n)) {
                    copiedMap.put(n, new Node(n.val));
                    que.offer(n);
                }

                copied.neighbors.add(copiedMap.get(n));
            }
        }

        return copiedMap.get(node);
    }
}

DFS 방식
기본적인 아이디어는 똑같고 Depth first라는 점만 다르다.
마찬가지로 copiedMap을 이용해서 origin/copy 쌍을 관리한다.

neighbors 순회 시 재귀를 이용해 파고든다.

class Solution {

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

        Map<Node, Node> copiedMap = new HashMap<>();

        copiedMap.put(node, new Node(node.val));
        dfs(node, copiedMap.get(node), copiedMap);

        return copiedMap.get(node);
    }

    public void dfs(Node origin, Node copy, Map<Node, Node> copiedMap) {
        for (Node n : origin.neighbors) {
            if (!copiedMap.containsKey(n)) {
                copiedMap.put(n, new Node(n.val));
                dfs(n, copiedMap.get(n), copiedMap);
            }
            copy.neighbors.add(copiedMap.get(n));
        }
    }
}