[프로그래머스] Lv.3 네트워크 (자바스크립트)

 

 

*모든 코드는 Javascript로 작성합니다.

*코드는 참고용으로만 봐주세요!

 

---

 

문제

 

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

 

 

 

해결방법

 

< Unionfind로 해결할 수 있는 문제> 

- computer[i][j]가 1이면 i, j 노드(=컴퓨터)를 unite 한다.

- 최종적으로 root가 자기 자신인 노드(=컴퓨터)의 개수를 카운팅한다.

 

 

 

 

 

코드

 

class Unionfind{     constructor(n){         this.par = Array.from({length: n}, ()=>-1);         this.siz = Array.from({length: n}, ()=>1);     }     root(x){         if (this.par[x] == -1){             return x;         }         return this.par[x] = this.root(this.par[x]);     }     unite(x, y){         var x_root = this.root(x);         var y_root = this.root(y);         if (x_root == y_root) return;         if (this.siz[x_root] < this.siz[y_root]){             [x_root, y_root] = [y_root, x_root] //swap x, y         }         this.par[y_root] = x_root;         this.siz[x_root] += this.siz[y_root];     }     size(x){         return this.siz[this.root(x)];     } } function solution(n, computers) {     var uf = new Unionfind(n);          for (let i = 0; i < n; i++){         for (let j = i+1; j < n; j++){             if (computers[i][j] == 1){                 uf.unite(i, j);             }         }     }          var count = 0;     for (let i = 0; i < n; i++){         if (uf.root(i) == i){             count++;         }     }          return count; }