[LeetCode] 133. Clone Graph

LeetCode - The World's Leading Online Programming Learning Platform

연결된 방향이 없는 그래프에서 노드의 참조가 주어집니다.
그래프의 복제본을 반환합니다.
그래프의 각 노드는 값(int)과 이웃 노드의 목록(List[Node])을 포함합니다.

 

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

 

문제접근

그래프를 탐색하며 주어진 node를 그대로 복사하여 반환하는 문제입니다.

 

BFS와 DFS로 접근해보았지만, visited처리를 어떻게 해야할지 찾지 못해 답안을 보고 이해하였습니다. 

 

BFS탐색을 하면서 해당 노드에 방문할때마다 값을 복사하면 되겠다고 생각했습니다.

BFS는 queue를 사용해 그래프를 탐색하는 알고리즘입니다.

Map을 사용해 방문했다면 queue에 넣지 않을것입니다. 

따라서 visited배열은 선언하지 않았습니다.

 

현재노드를 방문하며 이웃노드들을 추가하는게 전부입니다.

현재노드에 추가할때 HashMap에 value값인 graph에 추가되어 복사본을 return할 수 있습니다.

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

        HashMap<Node, Node> mp = new HashMap<>();
        mp.put(node, graph);

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

         while (!q.isEmpty()) {
            Node cur = q.poll();
            System.out.println("현재 노드 : " + cur.val );
            for (Node neighbor : cur.neighbors) {
                System.out.println("이웃 노드 : " + neighbor.val);
                if (!mp.containsKey(neighbor)) {
                    System.out.println("visited인 Map/ Queue에 추가할 노드 : " + neighbor.val);
                    mp.put(neighbor, new Node(neighbor.val));
                    q.offer(neighbor);
                }
                // 현재노드의 이웃들을 전부 추가
                final Node temp = mp.get(cur);
                temp.neighbors.add(mp.get(neighbor));
                System.out.println("현재노드 : " + temp.val + " 추가할 노드 : " + mp.get(neighbor).val);
            }
            System.out.println();
        }
        return graph;
    }

DFS 풀이

그래프 탐색 알고리즘은 DFS로 풀이한코드입니다.

 

mp에 Key로 노드가 있다면 그 값을 반환하고

없다면 새로 생성하여 정답을 받을 수 있습니다. 

HashMap<Node, Node> mp = new HashMap<>();
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (mp.containsKey(node)) return mp.get(node);

        mp.put(node, new Node(node.val));
        for (Node val : node.neighbors) {
            mp.get(node).neighbors.add(cloneGraph(val));
        }

        return mp.get(node);
    }

느낀점

이번문제는 어떻게 풀 수 있겠다라는 생각은 들었지만, 실제로 코딩으로 구현했을때

정답을 받기 너무 힘들었습니다.

 

그래프 탐색을 더 공부하고 연습해보아야 겠습니다.

참고

LeetCode - The World's Leading Online Programming Learning Platform