네트워크

네트워크 (프로그래머스)

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

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다.

예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고,

컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때

컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다.

따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때,

네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

풀이

인자로 네트워크의 갯수를 주는것을 이용하여

각 네트워크를 방문했는지 체크하는 변수를 만들어줍니다

A, B, C 네트워크가 있다고 가정할떄

반복문으로 모든 네트워크를 순회합니다

네트워크에 접속하기전에 해당 네트워크에 방문한적이 있는지 체크하는 조건문을 만들어 방문한적이 없을때만 접속합니다

먼저 1번쨰 반복문에서는 A네트워크에 접속하고 A네트워크랑 연결되어있는 네트워크들을 방문합니다

방문한 네트워크는 체크해둡니다

만약 A와 B 네트워크가 연결되어있으면 B네트워크도 방문합니다

2번째 반복문은 B네트워크 차례입니다

하지만 B네트워크는 A네트워크에 접속했을때 B네트워크와 연결되어있어서 접속한적이 있어 방문체크가 되어있기 때문에 넘어갑니다

3번째 반복문에서는 C네트워크 차례입니다

C네트워크는 방문한 기록이 없기때문에 접속합니다

이렇게 각 네트워크에 접속할때마다 카운트를 세주면 됩니다

step 1 => A 네트워크 <---> B네트워크 => count++ = 1

step 2 => B 네트워크 => A네트워크를 통해 방문한적이 있음 => 건너띄기

step 3 => C 네트워크 => count++ = 2

 

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

    function dfs(network) {
        visited[network] = true;
        computers[network].forEach((connected, network) => {
            if (connected === 1 && !visited[network]) dfs(network);
        });
    }

    for (let network = 0; network < n; network++) {
        if (visited[network]) continue;
        dfs(network);
        answer++;
    }

    return answer;
}