[Graph] Clone Graph

그래프 복제

LeetCode - The World's Leading Online Programming Learning Platform

연결된 무방향 그래프 의 노드에 대한 참조가 제공됩니다 .

그래프의 전체 복사본 (클론)을 반환합니다 .

그래프의 각 노드에는 이웃 노드의 값( int)과 목록( )이 포함되어 있습니다.List[Node]

클래스 노드 {
    공개 int 값;
    공개 목록<노드> 이웃;
}

 

테스트 케이스 형식:

단순화를 위해 각 노드의 값은 노드의 인덱스(1-인덱스)와 동일합니다. 예를 들어 첫 번째 노드는 val == 1, 두 번째 노드는 val == 2, 등등입니다. 그래프는 인접 목록을 사용하여 테스트 케이스에 표시됩니다.

인접 목록은 유한 그래프를 나타내는 데 사용되는 순서가 지정되지 않은 목록 의 모음입니다 . 각 목록은 그래프에 있는 노드의 이웃 집합을 설명합니다.

주어진 노드는 항상 가 있는 첫 번째 노드가 됩니다 val = 1. 복제된 그래프에 대한 참조로 지정된 노드의 복사본을 반환해야 합니다 .

 

예시 1:

입력: adjList = [[2,4],[1,3],[2,4],[1,3]]
 출력: [[2,4],[1,3],[2,4], [1,3]]
 설명: 그래프에는 4개의 노드가 있습니다.
첫 번째 노드(val = 1)의 이웃은 두 번째 노드(val = 2)와 네 번째 노드(val = 4)입니다.
두 번째 노드(val = 2)의 이웃은 첫 번째 노드(val = 1)와 세 번째 노드(val = 3)입니다.
3번째 노드(val = 3)의 이웃은 2번째 노드(val = 2)와 4번째 노드(val = 4)입니다.
4번째 노드(val = 4)의 이웃은 1번째 노드(val = 1)와 3번째 노드(val = 3)입니다.

예 2:

입력: adjList = [[]]
 출력: [[]]
 설명: 입력에 빈 목록이 하나 포함되어 있습니다. 그래프는 val = 1인 하나의 노드로만 구성되며 이웃이 없습니다.

예시 3:

입력: adjList = []
 출력: []
 설명: 이 그래프는 빈 그래프이며 노드가 없습니다.

 

제약:

• 그래프의 노드 수가 범위 내에 있습니다 [0, 100].
• 1 <= Node.val <= 100
• Node.val각 노드마다 고유합니다.
• 그래프에는 반복되는 간선이나 자가 루프가 없습니다.
• 그래프는 연결되어 있으며 해당 노드부터 모든 노드를 방문할 수 있습니다.

---

문제풀이

/*
// 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 {
    Node[] copyNodes = new Node[100];
    
    public Node cloneGraph(Node node) 
    {
        if (node == null) return null; 
        
        int ind = node.val-1;
        if (copyNodes[ind] == null) 
        {
            cndopyNodes[i] = new Node(node.val); 
            for (Node neighbor : node.neighbors) 
                copyNodes[ind].neighbors.add(cloneGraph(neighbor));
        }
        return copyNodes[ind]; 
    }
}

BFS 너비 우선 탐색 알고리즘을 사용하여 풀기로 했습니다.

1 <= Node.val <= 100

제약조건을 이용하기 위하여 new Node[100]의 복제 노드 배열을 생성하여 사용하였습니다.

root노드를 기준으로 인접 neughbors노드를 탐색하여 제귀방식으로 노드를 복사하였고

neighbor노드가 없으면 제귀메서드는 null을 반환하여 stack overflow를 막아 해결하였습니다.