Clone Graph (DFS)

이번 문제는 LeetCode의 Queue, Stack 튜토리얼 중 DFS를 다루는 두 번째 문제다.

Explore - LeetCode

BFS와 마찬가지로 DFS 역시 그래프에서 노드부터 노드까지 경로를 찾는 데 사용될 수 있다. 그러나 이 경로가 항상 최단경로라는 보장은 없으며 탐색 순서에 따라, 정확히는 그래프에서 이웃 노드를 참조하는 방식에 따라 달라질 수 있다.

 

BFS에서 Breadth First, 즉 넓이를 우선으로 했다면 DFS에서는 Depth First, 즉 깊이를 우선으로 하기 때문에 하나의 자식 노드를 발견하면 다른 자식 노드를 자료구조에 삽입하거나 참조하기 전에 해당 노드를 탐색한다. 그리고 그 자식 노드의 자식 노드에서도 동일하게 탐색하며 더 이상 탐색할 자식 노드가 없을 때까지 최대한 깊게 탐색한다. 그래서 Depth를 파고드는 방식으로 DFS라 불리는 것인데 이때 더 이상 탐색할 자식 노드가 없다는 것은 정말로 연결된 자식 노드가 없다는 것뿐 아니라 탐색해야 하는 자식 노드가 없다는 것에도 해당한다.

 

BFS, DFS를 설명할 때는 대부분 상하관계의 단방향 그래프를 예로 들기 때문에 자식 노드라고 표현하였지만 그래프 형태에 따라 이웃 노드, 심지어 방금 탐색했던 노드도 해당될 수도 있다. 만약 단방향 그래프라면 필요 없겠지만 양방향 그래프인 경우 DFS를 할 때는 탐색했던 노드를 기억해야 할 필요가 있다.

위와 같은 두 그래프가 있다고 할 때 노드 1에서는 노드 2로, 노드 2에서는 노드 3으로 처럼 순서대로만 탐색할 수 있다. 이 경우 탐색하다가 시작 노드(여기서는 노드 1)로 다시 돌아왔다면 탐색을 종료해도 될 것이다. 하지만 오른쪽 그래프 같은 경우 노드 1에서는 노드 2, 노드 4로, 노드 2에서는 노드 3, 노드 1로 아무렇게나 탐색할 수 있다. 그렇기 때문에 노드 1을 탐색하고 노드 2로 건너갔다고 해도 탐색했던 노드들을 기억하지 않으면 노드 2의 자식 노드로 취급되는 노드 1로 다시 돌아가서 탐색할 수 있다. 이는 바람직하지 않은 상황이며 이를 구별하는 것이 이번 문제의 목적이기도 하다.

 

이런 DFS는 Stack 자료구조를 활용하여 구현할 수 있는데 어떤 노드의 자식 노드를 탐색 대기 목록인 스택에 삽입할 때 노드 1, 노드 2, 노드 3 자식 노드가 있다면 노드들을 스택에 삽입하고 제일 최근에 삽입한 노드 3을 꺼내서 탐색한다. 그리고 노드 3의 자식 노드를 다시 스택에 삽입하는데 선입 후출(LIFO)의 스택 특성상 제일 나중에 삽입된 노드 3의 자식 노드들이 노드 1, 노드 2보다 먼저 처리되게 된다. 노드 3 쪽으로만 Depth를 파고 들어가는 것이다.

위의 예시를 보면 스택에서 꺼낸 노드 3의 자식 노드들이 스택에 삽입되면서 노드 1, 노드 2는 탐색 순위가 밀리는 것을 볼 수 있다. 만약 스택을 사용하지 않는다면 함수의 재귀 호출을 사용할 수 있지만 이 경우 메모리 오버플로우에 주의하여야 한다.

 

이번 문제는 문제 자체를 이해하는 것도 조금 까다롭기 때문에 문제 자체의 평가(추천/비추천)도 낮은 편에 속하는데 일단 문제에서 요구하는 것은 다음과 같다.

• 연결된 비 방향(connected undirected) 그래프가 있다.

• 이 그래프 중 하나의 노드가 주어진다.

• 이 노드를 이용하여 그래프의 깊은 복사(deep copy)를 수행한다.

• 깊은 복사된 그래프의 노드를 반환한다.

• 그래프의 노드는 int형 val 멤버와 ArrayList <Node> 형 neighbors 멤버를 가진다. neighbors 멤버는 해당 노드와 연결된 그래프를 가리킨다.

• 깊은 복사된 그래프는 노드들의 연결 상태(neighbors)나 값(val)이 바뀌면 안 된다. 하지만 매개변수로 전달받은 노드의 그래프와 다른 객체여야 한다.

즉 그래프의 노드 하나를 줄 테니 이를 이용하여 해당 노드의 그래프를 완전히 동일하게, 그러나 새로운 객체로 복사하여 그 그래프의 노드를 반환하라는 것이다. 그렇다면 이 문제에 DFS를 어떻게 활용해볼 수 있을까? 일단 위에서 언급한 것처럼 연결된 비 방향 그래프기 때문에 DFS로 탐색된 노드를 기억하려면 Set 자료구조가 필요하다. 그리고 주어진 노드는 복사해야 하는 그래프의 한 노드기 때문에 이 노드의 자식 노드(여기서는 이웃 노드)를 DFS를 이용하여 계속 탐색하면서 그래프의 전체를 탐색하는 방식으로 전체 그래프를 탐색, 복사할 수 있을 것이다.

 

하지만 그냥 이 문제를 풀게 되면 대부분의 경우 "You must return a copy of all the nodes in the original graph"라는 에러 메시지를 보게 될 것이다. 처음에는 이게 대체 무슨 의민가 해서 많이 헷갈렸는데 Discuss를 찾아보니 tip if you're oddly getting "You must return a copy of all the nodes in the original graph"과 같은 포스트를 찾을 수 있었다.

tip if you're oddly getting "You must return a copy of all the nodes in the original graph" - LeetCode Discuss

즉 문제에서는 확실하게 언급되지 않아 헷갈릴 수 있겠지만 문제에서 복사된 그래프를 확인할 때 각 노드의 값(val)과 이웃 노드(neighbors)만 확인하는 게 아니라 어떤 노드에서 가리키는 노드가 실제 노드와 동일한 노드인지 확인하고 있다. 이게 무슨 얘기냐면 노드 1과 노드 2가 노드 3을 이웃 노드로 가지고 있다고 할 때 노드 1에서 가리키는 노드 3과 노드 2에서 가리키는 노드 3이 동일한 객체인지를 확인한다는 것이다.

 

문제에서 요구하는 그래프를 복사하려면 아무것도 없는 노드에서 객체를 생성하며 그래프의 노드를 추가해가는 게 보통일 것이다. 그러면서 노드의 neighbors 멤버에 이웃 노드를 담기 위해 Node 클래스의 객체가 생성될 텐데 맨 처음에 문제를 풀었을 때는 해당 노드의 이웃 노드를 매번 새로운 객체로 생성하여 등록했다. 그 결과 그래프가 다음처럼 구축됐기 때문에 올바르지 않은 그래프라는 에러가 발생했던 것이다.

위의 그림에서 노드 1, 노드 2, 노드 3, 노드 4 자체의 관점에서만 본다면 복사된 그래프와 원본 그래프는 동일하다. 둘 다 같은 값을 가지고 있고 해당 노드에 연결된 이웃 노드들도 동일하다. 하지만 연결된 이웃 노드가 실제로 존재하는 그 노드가 아니기 때문에 문제에서 요구하는 조건과는 부합하지 않는다. 언급했듯이 나는 초반에 이 문제를 풀 때 해당 노드의 이웃 노드들을 매번 새로운 객체로 생성해서 등록했다. 그래서 위의 그림에서 Copied Graph처럼 기존에 존재하던 노드와는 별개의 노드가 생성되어 연결됐기 때문에 결과적으로 원본 그래프와는 다른 그래프가 생성되었다. 이 점을 빨리 알아차리지 못해서 문제를 푸는데 난관이 좀 있었던 것 같다.

 

이를 해결하기 위해서 특정 노드의 객체가 생성되었을 때 이를 저장할 수 있는 Map 자료구조를 사용하였다. 만약 Map에 해당 노드의 객체가 등록되어있지 않다면 새로 객체를 생성하고 Map에 저장한다. 반대로 이미 객체가 존재한다면 새로 생성하지 않고 Map에서 꺼내서 이웃 노드로 등록하거나 DFS 탐색을 수행한다. 물론 위에서 생성한 Set 자료구조에 이미 탐색한 노드는 기록해서 중복 탐색이 발생하지 않도록 해야 할 것이다.

 

그리고 마지막까지 몰랐던 것이 일단 시작 노드는 무조건 1번 노드(val이 1)로 주어지는데 이 노드도 객체를 생성해서 Map에 등록해야 한다는 것이다. DFS 탐색에서 Map에 객체를 넣고 빼는 것만 집중하고 있어서 정작 탐색 시작 노드를 까먹고 객체를 생성하지 않아서 이건 또 이것대로 시간을 많이 소모했다. 알고리즘 문제를 풀 때는 처음부터 끝까지 머릿속으로 코드가 어떻게 돌아가는지 떠올려보면서 작성하는 습관을 들여야겠다.

 

아무튼 이렇게 작성한 코드는 다음과 같다.

import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;


class Solution {
    Map<Integer, Node> copiedNodes = new HashMap<>();
    Set<Integer> visited = new HashSet<>();
    
    public Node cloneGraph(Node node) {
        if(node == null) return null;
        Node result = new Node(node.val);
        copiedNodes.put(1, result);
        cloneNeighbors(result, node);
        return result;
    }
    
    private void cloneNeighbors(Node targetNode, Node originalNode){
        if(visited.contains(targetNode.val)) return;
        visited.add(targetNode.val);
            
        originalNode.neighbors.forEach(neighbor -> {
            Node newNeighbor = null;
            if(copiedNodes.containsKey(neighbor.val)){
                newNeighbor = copiedNodes.get(neighbor.val);
            } else {
                newNeighbor = new Node(neighbor.val);
                copiedNodes.put(neighbor.val, newNeighbor);  
            }
            targetNode.neighbors.add(newNeighbor);              
            cloneNeighbors(newNeighbor, neighbor);
        });
    
    }
}

Stack 대신 재귀를 사용한 DFS를 적용했다. 매개변수로 주어지는 노드는 항상 노드 1이므로 이를 Map에 넣고 재귀 함수 cloneNeighbors를 호출한다. 해당 함수에서는 원본 그래프의 노드(originalNode)를 참조하여 해당 노드의 이웃 노드들을 복사된 노드에 똑같이 복사한다. 이때 Map에 containsKey() 메서드를 사용하여 해당 노드가 이미 객체로 생성되었는지 확인하고 있다.

 

비슷한 로직으로 Stack을 사용하면 다음과 같다.

import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;
import java.util.Stack;


class Solution {
    Stack<Node> stack = new Stack<>();
    Map<Integer, Node> copiedNodes = new HashMap<>();
    Set<Integer> visited = new HashSet<>();
    
    public Node cloneGraph(Node node) {
        if(node == null) return null;
        Node result = new Node(node.val);
        copiedNodes.put(1, result);
        stack.push(node);
        while(!stack.empty()){
            Node originalNode = stack.pop();
            
            if(visited.contains(originalNode.val)) continue;
            visited.add(originalNode.val);
            
            Node copiedNode = copiedNodes.get(originalNode.val);
            if(copiedNode == null) {
                copiedNodes.put(originalNode.val, new Node(originalNode.val));
            }
            
            originalNode.neighbors.forEach(neighbor -> {
                Node newNeighbor = null;
                if(copiedNodes.containsKey(neighbor.val)){
                    newNeighbor = copiedNodes.get(neighbor.val);
                } else {
                    newNeighbor = new Node(neighbor.val);
                    copiedNodes.put(neighbor.val, newNeighbor);  
                }
                stack.push(neighbor);
                copiedNode.neighbors.add(newNeighbor);
            });
        }
        
        return result;
    }

}

두 풀이 모두 메모리 사용량은 괜찮았지만 실행시간에서는 약간 뒤처졌는데 상위권의 풀이를 보면 다음처럼 cloneGraph 함수 자체를 재귀 호출하면서 푼 것을 볼 수 있다. 역시 Map 자료구조를 사용하고 있는데 특이한 것은 새로 생성된 노드에 이웃 노드를 추가할 때도 재귀 호출을 통해 추가하는 동시에 이웃 노드를 탐색하는 것을 볼 수 있었다.

class Solution {
    Map<Node, Node> map = new HashMap<Node, Node>();
    public Node cloneGraph(Node node) {
        if (node == null)
            return null;
        if (map.containsKey(node))
            return map.get(node);
    
            Node temp = new Node(node.val, new ArrayList<Node>());
            map.put(node, temp);
            for (Node neighbor : node.neighbors) {
                temp.neighbors.add(cloneGraph(neighbor));
            }
        return map.get(node);
    }
}

특히 이미 생성된 노드를 Map에 담을 때 노드의 값(val)을 사용하지 않고 원본 그래프 노드 객체 자체를 키로 사용하여 복사된 그래프 노드 객체를 값으로 담는 것이 인상적이었다. 정말 보고 배울 점이 많은 것 같다.