LeetCode: 133번 (Clone Graph) [JAVA]

문제 링크

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

Clone Graph - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 복제한 노드들을 담을 Node[] 배열 선언
2. dfs 기반 복제 함수 clone 구현. 해당 번호(val)의 노드가 앞서 선언한 배열에 존재하면 이를 반환하고, 그렇지 않다면 해당 인덱스의 node를 생성한 다음 반환
3. 해당 함수를 호출한 결과를 반환

 기존 주어진 node와 연결된 노드들을 모두 복사한 다음, 기존 node의 복사한 객체를 반환해야 하는 문제이다. 그리고 노드들의 연결 상태가 undirected graph이기 때문에, 기존 형태를 단순히 따라가며 복사하다보면 기존 노드를 계속 타고 가며 함수가 끝나지 않을 수도 있다. 그렇기 때문에 그래프 탐색 특성 상 중복 방문을 피해야하며, 기존의 연결관계를 모두 담아야 하기 때문에 dfs 방식으로 노드를 복사하는 방법을 사용했다.

 우선 복사한 노드들을 담을 Node 배열을 초기화 한 후, dfs 기반 복제 함수를 작성한다. 우선 노드들의 구분을 노드의 값(val)으로 할 수 있기 때문에 이를 배열의 인덱스로 활용하며, 해당 위치의 Node가 존재하면 앞서 생성한 노드이기 때문에 이를 반환한다. 반대로 null인 경우 새로 Node를 작성하는데, 우선 노드 속 값을 초기화 해주고, 이후 연결 관계를 설정하기 위해 연결된 노드들을 가져온다. 이 때 연결관계를 설정할 노드들 또한 복제해야 하기 때문에, 동일한 함수를 호출하며 연결관계에 추가해준다.

 이후 주어진 node의 복제 함수를 호출하며 이 결과값을 반환하면 된다.

 

class Solution {
    Node[] nodes;

    public Node cloneGraph(Node node) {
        nodes = new Node[101];

        if (node == null) {
            return null;
        } else {
            return clone(node);
        }
    }

    Node clone(Node node) {//dfs 기반 복제
        if (nodes[node.val] != null) {//이미 복제한 노드가 있으면
            return nodes[node.val];
        }

        nodes[node.val] = new Node(node.val);//초기화

        for (int i = 0; i < node.neighbors.size(); i++) {//neighbors 구성
            nodes[node.val].neighbors.add(clone(node.neighbors.get(i)));
        }

        return nodes[node.val];
    }
}

결과