문제

아래 그림과 같이 무방향 그래프의 한 노드가 주어졌을 때 주어진 노드가 속한 무방향 그래프를 깊은복사하는 것이 문제이다.

이미지 출처: LeetCode

그림과 같이 완전히 새로운 노드를 생성해 원래 그래프와 똑같은 모양으로 연결을 시켜야한다.

첫 번째 풀이 - 실패

그래프를 복사하는 건 처음이다. 가장 처음 생각난 방법은 BFS를 활용하는 것이었다. 시작 노드부터 너비 우선 탐색으로 노드를 방문하면서 방문하지 않은 노드이면 복사하는 그래프에 새로운 노드를 연결시키는 것이다.

while !queue.isEmpty()
	Node originNode = originQ.poll()
    Node copyNode = copyQ.poll()
    
    for neighbor : originNode.neighbors
    	if !visit[neighbor.val]
        	visit[neighbor.val] = true
            
        	Node newCopyNode = new Node(neighbor.val)
            copyNode.neighbors.add(newCopyNode)
            newCopyNode.neighbors.add(copyNode)
            
            originQ.add(neighbor)
            copyQ.add(neighbor)

하지만 연결이 안되는 노드들이 존재한다. 예를들어 위 문제에서 주어진 그래프에서 3번 노드까지 탐색했을 때 4번 노드는 이미 방문한 노드이기 때문에 두 노드는 연결될 수 없다.

이를 해결하기 위해 방문한 neighbor일 때 copyNode에 같은 번호의 노드가 연결되어 있지 않으면 연결하려했다. 이미 방문한 neighbor이면 그와 같은 번호의 copyNode가 생성되었을 것이다. 하지만 현재 copyNode에서는 연결하려는 노드를 알 수 없기 때문에 이 방법으로 두 노드를 연결할 수 없다.

3번 노드까지 방문했을 때 3번과 4번에 해당하는 copyNode는 이미 생성되어 있을 것이다. 하지만 복사된 3번 노드 입장에서는 4번에 해당하는 copyNode를 알 방법이 없기 때문에 두 노드를 연결할 수 없다.

두 번째 풀이

두 번째 풀이에서는 BFS를 활용하는 것 동일하나 연결 과정을 좀 더 단순화시켰다. 해당 노드에 방문했을 때 해당 노드의 neighbors에만 노드를 추가한다. 이 과정에서 neighbor에 해당하는 copyNode가 생성되지 않았으면 생성한다(생성하지만 neighbor에 해당하는 copyNode에는 현재 방문한 copyNode를 추가하지 않는다.).

이 때, 노드끼리 연결되지 않으면 알 수 없는 문제를 해결하기 위해 Node[]을 선언해 번호에 따라 copyNode를 가리키도록해 언제든지 접근해 사용할 수 있도록 했다.

copyNode들끼리는 아직 연결되어있지 않기 때문에 서로 알 수 없거나 알기 위해 현재 copyNode부터 연결을 따라가 찾아야한다.

노드의 개수를 n, 각 노드에 연결된 neighbor의 수를 m이라고 했을 때 시간복잡도는 $O(nm)$을 갖는다.

class Solution {
    public Node cloneGraph(Node node) {
      if (node == null)
        return null;
      
      Node[] copyNodes = new Node[101];
      copyNodes[node.val] = new Node(node.val);

      Queue<Node> queue = new ArrayDeque<>();
      boolean[] visit = new boolean[101];

      queue.add(node);
      visit[node.val] = true;

      while (!queue.isEmpty()) {
        Node cur = queue.poll();
        Node copyNode = copyNodes[cur.val];

        for (Node neighbor : cur.neighbors) {
          if (copyNodes[neighbor.val] == null) {
            copyNodes[neighbor.val] = new Node(neighbor.val);
          }

          copyNode.neighbors.add(copyNodes[neighbor.val]);

          if (!visit[neighbor.val]) {
            visit[neighbor.val] = true;
            queue.add(neighbor);
          }
        }
      }

      return copyNodes[node.val];
    }
}

결과는 여러번 제출했을 때 실행시간 24ms, 메모리 사용량 41.4MB까지 기록하였다. 각각 100% Beats, 97.9% Beats이다.

위 두 기록이 같이 나온 적은 없다. 실행시간이 짧으면 메모리 사용량이 늘고 실행시간이 길면 메모리 사용량이 적게 나왔다.

다른 Solution을 참고하니 DFS로 해결한 풀이가 많았다. 웬만해서 DFS로 풀 수 있는 문제는 BFS로 풀 수 있으며 그 반대도 가능하다(가끔식 안되는 문제도 존재한다).