LeetCode 133: 방문한 노드를 기억하며 그래프 복사하기

원본과 복제 노드를 짝지어 둡니다

Clone Graph 문제와 그래프 예시

주어진 그래프를 복사하는 문제입니다. 당시에는 깊이 우선 탐색(DFS)으로 이웃 노드를 따라가면서 복제한 노드를 해시맵에 저장하는 방식으로 풀었습니다.

visited의 키는 원본 노드이고 값은 그 노드를 복제한 새 노드입니다. 입력이 null이면 그대로 null을 반환합니다. 이미 복제한 노드라면 새로 만들지 않고 맵에 저장된 노드를 반환합니다.

처음 만난 노드는 값부터 복사해 만든 다음, 이웃을 탐색하기 전에 맵에 넣습니다. 그래야 순환 경로로 같은 노드에 돌아와도 재귀 호출이 계속 이어지지 않습니다. 각 이웃은 재귀로 복사해 새 노드의 이웃 목록에 추가합니다.

코드

아래는 제출한 코드입니다. Node는 문제에서 제공하는 것을 그대로 사용합니다.

Java

class Solution {
    private HashMap <Node, Node> visited = new HashMap <> ();
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);

        Node cloneNode = new Node(node.val, new ArrayList());
	    visited.put(node, cloneNode);

        for (Node neighbor: node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        
	    return cloneNode;
    }
}