문제

연결된 무방향 그래프의 첫번째 노드가 주어졌을때, 그래프 전체를 깊은 복사하여 반환한다.

구현 전 예상 풀이

dfs로 탐색한다.
1. 노드를 방문하면 새로운 노드 객체를 생성하고, 값을 복사한다.
2. 방문한 노드를 배열에 저장한다.
3. 인접 노드를 방문한다.
4. 이미 방문한 노드라면 배열에 저장된 노드를 반환한다.
5. 백트래킹하면서 반환 받은 인접 노드를 이웃 노드 리스트에 추가한다.

구현 코드

class Solution {
    Node[] graph = new Node[101];

    public Node cloneGraph(Node node) {
        return clone(node);
    }

    private Node clone(Node target) {
        int v = target.val;

        if (graph[v] == null) {
            graph[v] = new Node(v);

            for (Node neighbor : target.neighbors) {
                Node clone = clone(neighbor);
                graph[v].neighbors.add(clone);
            }
        }

        return graph[v];
    }
}

개선 코드

node가 null일 경우 NullPointerException 예외가 발생하여 예외처리 코드를 추가하였다.
또한 이웃이 없을경우 바로 Node(1) 객체를 반환하는 코드도 추가하였다.

class Solution {
    Node[] graph = new Node[101];

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        } else if (node.neighbors == null) {
            return new Node(1);
        }
        return clone(node);
    }

    private Node clone(Node target) {
        int v = target.val;

        if (graph[v] == null) {
            graph[v] = new Node(v);

            for (Node neighbor : target.neighbors) {
                Node clone = clone(neighbor);
                graph[v].neighbors.add(clone);
            }
        }

        return graph[v];
    }
}

133. Clone Graph
참고한 풀이 링크