[프로그래머스 Level 3] 네트워크 - JavaScript

🔗 문제 링크

 

✏️ 풀이

function solution(n, computers) {
    const visited = Array(n).fill(false);
    
    const dfs = (start) => {
        const stack = [start];
        while (stack.length) {
            const index = stack.pop();
            if (!visited[index]) {
                visited[index] = true;
                computers[index].forEach((v, i) => {
                    if (i !== index && v) {
                        stack.push(i);
                    } 
                });
            }
        }
    }
    let count = 0;
    computers.forEach((v, i) => {
        if (!visited[i]) {
            dfs(i);
            count++;
        }
    });
    return count;
}

컴퓨터 목록을 순회하면서 방문하지 않은 컴퓨터가 있으면 DFS를 해서 해당 컴퓨터와 연결된 모든 다른 컴퓨터들을 탐색한다. 이렇게 하면 네트워크의 연결 여부와 관계없이 모든 컴퓨터를 한 번씩 순회할 수 있다.

 

하나의 컴퓨터에서 DFS를 하면 해당 컴퓨터와 동일한 네트워크 상에 있는 모든 컴퓨터를 순회하게 되므로, DFS를 실행한 횟수가 곧 네트워크의 개수가 된다. 따라서, DFS를 할 때마다 count를 증가시켜서 출력하면 된다.

 

 

💡 재귀로 DFS하기

function solution(n, computers) {
    const visited = Array(n).fill(false);
    
    const dfs = (node) => {
        visited[node] = true;
        computers.forEach((relation, adjNode) => {
            if (relation[node] && !visited[adjNode]) {
                dfs(adjNode);
            }
        });
    }
    let count = 0;
    computers.forEach((_, node) => {
        if (!visited[node]) {
            dfs(node);
            count++;
        }
    });
    return count;
}