📌 문제 설명

네트워크 문제 보기

📌 문제 접근

간접적으로 연결된거까지 모두 같은 네트워크 상에 있다고 할 때, 힌트를 얻었다.

물론, 알고리즘 고득점 Kit 상 BFS/DFS로 구분되어 있었지만, 특정 경로를 일일히 체크 안해도 되는데 굳이 완전 탐색을 해야할까?

union 연산으로 원시 그룹들을 찾으면 되지 않을까? 따라서 Union-find 알고리즘을 사용해봤다.

📌 내가 작성한 코드

function solution(n, computers) {
  const parentIdx = Array.from({ length: n }, (_, i) => i);
  const findParentIdx = (idx) => {
    if (parentIdx[idx] === idx) return idx;
    return findParentIdx(parentIdx[idx]);
  };
  const union = (a, b) => {
    const parentA = findParentIdx(a);
    const parentB = findParentIdx(b);
    if (parentA <= parentB) parentIdx[parentB] = parentA;
    else parentIdx[parentA] = parentB;
  };
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      if (computers[i][j]) union(i, j);
    }
  }
  return new Set(parentIdx.map((_, i) => findParentIdx(i))).size;
}

📌 시간 복잡도

• 모든 컴퓨터 쌍을 확인하며 union 연산을 수행: O(N^2 × α(N)) (α는 역 아커만 함수로 거의 상수)
• 최종적으로 각 노드의 루트를 찾는 과정: O(N × α(N))
• 전체 시간 복잡도: O(N^2)

📌 참고 링크

• Set

• Union-Find