[알고리즘]네트워크

문제

문제 링크

코딩테스트 연습 - 네트워크 | 프로그래머스 (programmers.co.kr)

풀이

이번 문제는 연결된 컴퓨터 네트워크의 갯수를 구하는 문제이다. 어떻게든 컴퓨터 간에 간접적으로 연결이 되어있으면 하나의 네트워크라고 했기 때문에, 사실상 이 문제는 따로 분리된 컴퓨터 그룹이 몇 개나 있는가에 대해 묻는 문제나 마찬가지이다.

이 문제는 BFS를 사용해서 하나의 컴퓨터에서 시작하여 그 컴퓨터와 연결된 모든 컴퓨터를 찾을 때까지 진행이 되기 때문에 BFS가 한 번 실행될 때마다 1개의 네트워크가 존재한다는 것을 의미한다.

일단 중복해서 컴퓨터를 방문하는 일이 없도록 visited라는 boolean 배열을 선언해두고, 0부터 n-1까지 모든 ‘방문하지 않은’ 컴퓨터를 대상으로 BFS를 실행하였다. 중간에 간접적으로 연결된 컴퓨터들은 자신의 차례가 오기 전에 방문 처리가 될 것이므로 solution 함수 내에서는 BFS가 실행되지 않을 것이다.

코드

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