133. Clone Graph (bfs,dfs)

＜접근법＞

dfs 혹은 bfs를 통한 그래프의 전체 탐색을 따라가면서 중간 중간 Node를 생성하여 연결하면 된다.

 

<중간 문제점>

bfs 를 선택하고 정석적으로 큐를 사용하여 Queue가 빌 때까지 반복을 하는 동안 노드를 새롭게 생성하는 과정 속 에서 기존에 만들어진 노드들이 연결되지 않고 각각의 경우에 모든 노드가 다시 생성되어 전혀 연결되지 않는 문제점이 있었다. 

 

<최종 코드> 

BFS 너비 우선 탐색

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public Node cloneGraph(Node node) {
        if(node==null) return null;
        Node ans = new Node(node.val);
        Queue<Node> queue = new LinkedList<>();
        HashMap<Integer,Node> visit = new HashMap<>();
        queue.add(node);
        visit.put(ans.val,ans);

        // bfd 너비 우선 탐색
        while(!queue.isEmpty()){
            Node cur = queue.poll();

            for (Node neighbor:cur.neighbors) {
                if(!visit.containsKey(neighbor.val)) {
                    // visit를 활용하여 새로운 노드를 만들고
                    visit.put(neighbor.val,new Node(neighbor.val));
                    queue.add(neighbor);
                }
                // 만들어진 노드를 기존의 노드와 연결 시킴
                visit.get(cur.val).neighbors.add(visit.get(neighbor.val));
            }
        }

        return ans;
    }
}

DFS 깊이 우선 탐색

import java.util.*;

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

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public void DFS(Node cur,HashMap<Integer,Node> visit){
        for (Node neighbor:cur.neighbors) {
            if(!visit.containsKey(neighbor.val)) {
                // visit를 활용하여 새로운 노드를 만들고
                visit.put(neighbor.val,new Node(neighbor.val));
                DFS(neighbor,visit);
            }
            // 만들어진 노드를 기존의 노드와 연결 시킴
            visit.get(cur.val).neighbors.add(visit.get(neighbor.val));
        }
    }
    public Node cloneGraphDFS(Node node) {
        if(node==null) return null;
        Node ans = new Node(node.val);
        HashMap<Integer,Node> visit = new HashMap<>();
        visit.put(ans.val,ans);
        DFS(node, visit);

        return ans;
    }
}