[LeetCode] 133. Clone Graph - Java

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

Clone Graph - LeetCode

---

문제

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

 

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

 

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.

 

Constraints:

• The number of nodes in the graph is in the range [0, 100].
• 1 <= Node.val <= 100
• Node.val is unique for each node.
• There are no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.

---

풀이

풀이 과정

무방향 그래프 node가 주어질 때 그래프의 복사본을 return하는 문제이다.
동일한 그래프를 return 하여서는 안되고 이웃한 노드의 순서 또한 변해서는 안된다.

무방향 그래프에서 이웃 노드를 탐색할 때 이미 방문했던 노드를 방문할 시 탐색을 중지하기 위해서 탐색한 데이터를 저장할 Map을 전역 변수로 선언한다.

// 방문한 노드를 기억할 Map 선언
Map<Node, Node> visited = new HashMap<>();

 

우선 주어진 node가 빈 값인 경우 탐색할 필요없이 null을 바로 return한다.

// 빈 값이 들어오는 경우 null을 반환
if(node == null) return null;

 

이미 방문한 노드를 탐색하는 경우 map에 저장된 데이터를 반환한다.

// 이미 방문한 노드인 경우 해당 노드를 반환
if(visited.containsKey(node)){
    return visited.get(node);
}

 

처음 방문한 노드인 경우에는 새로운 노드를 생성하여 현재 탐색중인 노드의 복사본을 생성하고 현재 노드에 대한 방문 여부를 추가한다.
그 다음 현재 탐색 노드의 이웃 노드를 재귀적으로 탐색하며 복사본의 이웃 노드에 추가한다.

// 처음 방문한 노드인 경우
// 새로운 노드를 생성
Node clone = new Node(node.val, new ArrayList<Node>());
// 방문 여부 업데이트
visited.put(node, clone);
// 원본의 이웃 노드 탐색하며 복사본의 이웃 노드에 추가
for(Node neighbor : node.neighbors){
    clone.neighbors.add(cloneGraph(neighbor));
}

 

모든 복사 과정이 끝난 복사본을 최종 반환한다.

// 복사본을 반환
return clone;

---

최종 코드

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

class Solution {
    // 방문한 노드를 기억할 Map 선언
    Map<Node, Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        // 빈 값이 들어오는 경우 null을 반환
        if(node == null) return null;

        // 이미 방문한 노드인 경우 해당 노드를 반환
        if(visited.containsKey(node)){
            return visited.get(node);
        }

        // 처음 방문한 노드인 경우
        // 새로운 노드를 생성
        Node clone = new Node(node.val, new ArrayList<Node>());
        // 방문 여부 업데이트
        visited.put(node, clone);
        // 원본의 이웃 노드 탐색하며 복사본의 이웃 노드에 추가
        for(Node neighbor : node.neighbors){
            clone.neighbors.add(cloneGraph(neighbor));
        }

        // 복사본을 반환
        return clone;
    }
}

---