해당 문제는 자료구조: 트리, 힙에서 설명한 바 있는 union-find를 이용하는 문제이다. union-find를 각각의 루트로 연결된 서로소 집합이 나오고, 서로소 집합의 갯수가 곧 정답이 된다.

그래서 생각나는 대로 간단하게 union-find를 해서 아래와 같이 구현을 했었는데...

function solution(n, computers) {
    var answer = 0;
    const parentsArray = Array.from({length:n}, (e,i)=>i)
    for (i=0; i<n; i++) {
        for(j=0; j<n; j++){
            if(computers[i][j] === 1){
                const newParent = findParent(j, parentsArray)
                if(parentsArray[i] > newParent) parentsArray[i] = newParent
            }
        }
    }
  
    const set = new Set(parentsArray)

    return set.size;
}

function findParent(index, array) {
  if(array[index] == index) return index
  else if(array[index] < index) return findParent(array[index], array)
}

일부 테케만 통과하고 에러가 난다?
당연히 같은 네트워크인데도 부모 노드가 달라서 그러겠거니 해서 한번 더 돌렸는데

    const parentsArray = Array.from({length:n}, (e,i)=>i)
    for (i=0; i<n; i++) {
        for(j=0; j<n; j++){
            if(computers[i][j] === 1){
                const newParent = findParent(j, parentsArray)
                if(parentsArray[i] > newParent) parentsArray[i] = newParent
            }
        }
    }
    for (i=0; i<n; i++) {
        for(j=0; j<n; j++){
            if(computers[i][j] === 1){
                const newParent = findParent(j, parentsArray)
                if(parentsArray[i] > newParent) parentsArray[i] = newParent
            }
        }
    }

두 번 union을 했음에도 여전히 일부 테스트 케이스가 오답이다. (결과적으로 3번 union을 하니까 모든 테스트 케이스를 통과했다.)

해설

먼저 위의 로직은 제대로된 union-find가 아니다.
그리고 아래와 같은 테스트 케이스를 통과하지 못한다
(0-2 , 1-2)
이 경우 2번 노드를 중심으로 0, 1 노드가 이어져있다.
부모 배열은 [0, 1, 0]으로 업데이트 된다.

union-find 알고리즘

1. 연결된 모든 노드를 방문한다.
2. 만일 연결된 노드들의 부모가 다르면, 연결된 노드의 부모 중 더 값이 작은 부모로 부모를 합친다.

위의 알고리즘은 '1. 연결된 모든 노드를 방문한다'는 조건이 충족되지 않기 때문에 에러가 발생한다. 반복문을 1, 2, 3번 반복할수록 테스트 케이스를 통과하는 갯수가 늘어나는 것도 1번 조건의 충족에 가까워지기 때문이다. n번 반복하면 depth가 n인 조건이 충족된다. ([0, 1, 0]의 경우 depth가 2이다.)

1번 조건을 충족하면서, 2번 로직을 충족시키도록 코드를 수정해보자.
이제야 union-find 알고리즘이 구현되었다.

function solution(n, computers) {
    let answer = 0  
    const rootArray = Array.from({length:n}, (e,i)=>i);
    function findParent(index) {
      if(rootArray[index] === index) {
        return index;
      }
      return rootArray[index] = findParent(rootArray[index]);
    }

    for(let i=0; i<n; i++) {
        for(let j=i+1; j<n; j++) {
            if(computers[i][j] === 1) {
                const root1 = findParent(i);
                const root2 = findParent(j);
                if(root1 !== root2) {
                    rootArray[root2] = root1;
                }
            }
        }
    }
    rootArray.forEach((e,i)=>{ 
        answer += (e===i)
    })
    return answer
    // const set = new Set(rootArray.map((r) => findParent(r)));
    // return set.size;
}

위 로직에서 findParent가 재귀적으로 호출된다. 그러면서 return rootArray[index] = findParent(rootArray[index]);로 rootArray를 직접 접근하여 변경하는 sideEffect가 존재한다. 해당 sideEffect와 함께 rootArray는 자신이 속한 요소들의 부모 중 최솟값 가진 녀석의 부모로 자동 갱신된다.(그래서 이름이 rootArray다.) 이를 경로 압축이라고 부른단다. 경로 압축을 하면 depth가 자동으로 줄어들기에 결과적으로 findParent가 재귀적으로 호출되는 경우가 줄어 시간복잡도도 줄어든다.

문제의 답은 서로소 집합의 갯수이며, 이는 곳 루트 노드의 갯수이다. 최종 결과값을 리턴하는 방식에는 두가지가 있다.
하나는 rootArray.map((r) => findParent(r))으로 findParent를 최종 실행하는 것이다. rootArray가 자동으로 갱신되었지만, depth가 2인 경우가 남아있을 수 있다. 이를 마지막으로 갱신시켜주는 것이다. rootArray배열을 set안에 넣어 set의 size를 반환하면 서로소 집합의 갯수가 나온다.

두번째는 저장된 값과 인덱스가 같으면, 루트 인덱스이므로 해당 경우의 갯수를 반환하는 것이다.

dfs 끼얹기

위 코드에서 '연결된 모든 노드를 방문'하는 부분을 이중 반복문으로 구현했다.
이중 반복문이 아닌 dfs로 구현할 수 있다. 이중 반복문은 O(n^2)(경로압축을 사용하면 O(n log n)), DFS는 O(n)의 시간복잡도를 가진다. 하지만 실제 성능의 측면에서 보자면 이중 반복문을 이용한 방식에서도 '경로 압축'이라는 memoization을 활용했기에 성능상 차이는 없다.(오히려 이중 반복문 측이 성능이 더 좋았다.)

function solution(n, computers) {
  let answer = 0
  const visited = new Array(n).fill(false);
  const rootArray = Array.from({ length: n }, (e, i) => i);

  function dfs(node) {
    if (visited[node]) return;
    visited[node] = true;

    for (let i = 0; i < n; i++) {
      if (computers[node][i] === 1) {
        const root1 = findParent(node);
        const root2 = findParent(i);
        if (root1 !== root2) {
          rootArray[root2] = root1;
        }
        dfs(i);
      }
    }
  }

  function findParent(index) {
    if (rootArray[index] === index) {
      return index;
    }
    return (rootArray[index] = findParent(rootArray[index]));
  }

  for (let i = 0; i < n; i++) {
    dfs(i);
  }

  rootArray.forEach((e,i) => answer += (e===i))
  return answer
}