[알고리즘] LeetCode - Clone Graph

LeetCode - The World's Leading Online Programming Learning Platform

문제 설명

• 무방향 그래프의 하나의 노드가 주어진다.
• 노드는 val과 연결된 노드의 list로 이루어져 있다.
• 무방향 그래프를 깊은 복사하여 처음 주어진 노드의 val 값과 동일한 복사한 노드를 반환해야 한다.
• 노드의 각 val 값은 중복된 값이 없으며 1 <= val <= 100 의 범위를 가진다.

문제 해결

• 처음 주어지는 node의 값이 null 이면 탐색할 수가 없으므로 null을 반환한다.
• 깊은 복사한 노드의 값을 저장할 배열을 선언하여 노드를 저장한다.
• 너비 우선 탐색 (BFS)을 하면서 인접 노드들을 복사하여 현재 노드에 연결한다. 
• 만약 인접 노드를 만들지 않았으면 만들고, 있는 경우에는 그대로 연결한다.
• 다음 노드를 방문하지 않았으면 Queue에 삽입하여 다음번에 탐색할 수 있도록 한다.
• 탐색을 끝내고 처음 주어진 노드의 val 값과 동일한 복사한 노드를 반환한다.

시간 복잡도

• O(NM)

풀이 코드

class Solution {
    static Node[] nodes;

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

        nodes = new Node[101];
        nodes[node.val] = new Node(node.val);

        return bfs(node); 
    }

    static Node bfs(Node node) {
        Queue<Node> q = new ArrayDeque<>();
        boolean[] v = new boolean[101];

        q.add(node);
        v[node.val] = true;

        while(!q.isEmpty()) {
            Node now = q.poll();
            Node copyNode = nodes[now.val];

            for (Node next : now.neighbors) {
                if (nodes[next.val] == null) {
                    nodes[next.val] = new Node(next.val);
                }

                copyNode.neighbors.add(nodes[next.val]);

                if (!v[next.val]) {
                    v[next.val] = true;
                    q.add(next);
                }
            }
        }
        return nodes[node.val];
    }
}

결과

시간	메모리
26 ms	41.6 MB