[Javascript/자바스크립트] (프로그래머스) 네트워크

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

코드

3가지 버전으로 코드를 작성했다. 셋 다 정답 코드이다.

양방향 큐를 이용한 BFS

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

    const bfs = (start)=>{
        const q = [start];
        visited[start] = true
        while(q.length>0){
            const now = q.shift();
            for(let i=0;i<n;i++){
                if(now === i) continue;
                if(computers[now][i] === 1 && !visited[i]){
                    q.push(i);
                    visited[i] = true;
                }
            }
        }
    }

    for(let i=0;i<n;i++){
        if(!visited[i]){
            bfs(i)
            answer++;
        }
    }
    return answer;
}

재귀를 이용한 DFS

function solution2(n, computers){
    let answer = 0;
    const visited = new Array(n).fill(false);

    const dfs =(node)=>{
        visited[node] = true;
        for(let i=0;i<n;i++){
            if(node===i) continue;
            if(computers[node][i] === 1 && !visited[i]){
                dfs(i)
            }
        }
    }

    for(let i=0;i<n;i++){
        if(!visited[i]){
            dfs(i)
            answer++;
        }
    }
    return answer;
}

스택을 이용한 DFS

function solution3(n, computers){
    let answer = 0;
    const visited = new Array(n).fill(false);

    
    const dfs =(root)=>{
        const stack = [root];
        visited[root] = true;
        while(stack.length>0){
            const top = stack.pop();
            for(let i=0;i<n;i++){
                if(top === i) continue;
                if(computers[top][i] === 1 && !visited[i]){
                    stack.push(i)
                    visited[i] = true;
                }
            }
        }
    }

    for(let i=0;i<n;i++){
        if(!visited[i]){
            dfs(i)
            answer++;
        }
    }
    return answer;
}

 

셋 다 시간 복잡도는 최악의 경우에 O(n^2)이고, 공간 복잡도는 O(n)으로 동일하다. 그러니까 이 문제에서는 그냥 취향에 따라서 골라서 사용하면 된다.