Portfolio

문제

풀이

은찬

Union-Find가 아닌 DFS로 풀었는데, union-find로 한번 풀어보겠습니다~


function solution(n, computers) {
    let answer = 0;
    
    const visited = Array(n).fill(false);
    
    const dfs = (i) => {        
        for(let j = 0; j < n; j++){
            if(i !== j && !visited[j] && computers[i][j]){
                visited[j] = true;
                dfs(j);
            }
        }
    }
    
    for(let i = 0; i < computers.length; i++){
        if(!visited[i]){
            visited[i] = true;
            answer++;
            
            dfs(i);
        }
    }
    
    return answer;
}


function solution(n, computers) {
    let answer = 0;
    const parent = Array(n + 1).fill(-1);
    
    const getParent = (n) => {
        if(parent[n] === n){
            return n;
        }
        
        return parent[n] = getParent(parent[n]);
    }
    
    const unionParent = (a, b) => {
        const aParent = getParent(a);
        const bParent = getParent(b);
        
        if(aParent === bParent){
            return;
        }
        else if(aParent < bParent){
            parent[bParent] = aParent;
        }
        else{
            parent[aParent] = bParent;
        }
    }
    
    for(let i = 0; i < n; i++){
        parent[i] = i;
    }
    
    for(let i = 0; i < computers.length; i++){
        for(let j = 0; j < n; j++){
            if(i === j){
                continue;
            }
            
            if(computers[i][j]){
                unionParent(i, j);
            }
        }
    }
    
    for(let i = 0; i < n; i++){
        if(parent[i] === i){
            answer++;
        }
    }
    
    return answer;
}

현석


function solution(n, computers) {
    const visited =  Array.from({length: n}).fill(false)
    const stack = []
    let answer = 0;
    
    for (let i = 0; i < n; i++) {
        if (visited[i]) continue;
        
        stack.push(i);
        
        while (stack.length) {
            const computer = stack.pop();
            for (let j = 0; j < n; j++) {
                if (i === j || visited[j]) continue;
                
                if (computers[computer][j]) {
                    visited[j] = true;
                    stack.push(j)
                }
            }
        }
        answer++;
    }
    return answer
}

재영


const findParent = (x, parent) => parent[x] === x ? x : findParent(parent[x], parent);
const updateParent = (a, b, parent) => {
  const parentA = findParent(a, parent);
  const parentB = findParent(b, parent);
  if (parentA < parentB) parent[parentB] = parent[parentA];
  if (parentB < parentA) parent[parentA] = parent[parentB];
};

const solution = (n, computers) => {
  const parent = Array.from({ length: n }, (_, idx) => idx);
  computers.forEach((arr, rowIdx) => {
    arr.forEach((value, colIdx) => {
      if (rowIdx === colIdx) return;
      if (value) updateParent(rowIdx, colIdx, parent);
    });
  });
  return [...new Set(parent.filter((val, idx) => val === idx))].length;
};

가영


function solution(n, computers) {
    let answer = 0;
    let check = Array(n).fill(false);

    for(let computer = 0; computer < n; computer++) {
        if(!check[computer]) {
            findNetwork(computer);
            //한번의 방문이 끝나면 네트워크 수 1개 카운트
            answer++;
        }
    }

    //컴퓨터를 방문했는지 체크하면서 더 이상 방문할 수 있는 컴퓨터가 없으면 종료하는 재귀함수
    function findNetwork(curr) {
        if(check[curr] === true) return;

        check[curr] = true;
        for(let next = 0; next < n; next++) {
            if(computers[curr][next] === 1 && curr !== next) {
                findNetwork(next);
            }
        }
    }

    return answer;
}

효성


function solution(n, computers) {
    const getParent = (arr, x) => {
        if(arr[x] === x) return x;
        return arr[x] = getParent(arr, arr[x]);
    }
    
    const unionParent = (arr, a, b) => {
        a = getParent(arr, a);
        b = getParent(arr, b);
        
        if(a < b) {
            arr[b] = a;
        }
        else if (a === b) {
            return;
        }
        else {
            arr[a] = b;
        }
    }
    
    let answer = 0;
    let parent = Array(n).fill(false);
    
    for(let i = 0; i < n; i++){
        parent[i] = i;
    }

    for(let i = 0; i < n; i++){
        for(let j = 0; j < n; j++){
            if(i === j){
                continue;
            }

            if(computers[i][j]){
                unionParent(parent, i, j);
            }
        }
    }
        
    for(let i = 0; i < n; i++){
        if(parent[i] === i){
            answer++;
        }
    }
    
    return answer;
}