[Javascript] 프로그래머스 - 네트워크

목차

1. 문제 설명

2. 문제 풀이

3. 전체 코드

---

1. 문제 설명

n 개의 컴퓨터가 있을 때, 네트워크 개수를 계산한다.

☁ 네트워크란 컴퓨터가 연결된 형태를 의미한다.

if) A - B 와 B - C 가 연결되어 있다면 A - B - C는 하나의 네트워크 안에 있다고 할 수 있다.

 

입출력

 => n 개의 컴퓨터, 그리고 컴퓨터의 연결 정보가 주어질 때, 네트워크의 개수를 리턴한다.

 

첫번째 예시

 

두번째 예시

---

2. 문제 풀이

각 노드의 연결과 관련된 문제이므로, dfs 로 해결하였다.

1) dfs 를 한번 호출했을 때, 연결된 컴퓨터를 모두 방문할 수 있다.

2) 연결되지 않은 컴퓨터는 다시 dfs 를 호출해야 한다.

 

초기화

 

dfs 함수

 

dfs 함수를 호출하는 부분

 

시간복잡도

1) 전체 네트워크 탐색 과정 → O(N)
2) 한번의 dfs 에서 for 문으로 순회하는 데 걸리는 시간 → O(N)
👉 O(N의 제곱)

이 때, 컴퓨터의 최대 개수는 200 이하이므로, 시간은 충분했다.

---

3. 전체 코드

function solution(n, computers) {
    var answer = 0;
    
    var visited = Array.from({length: n}, (v)=> false); // 컴퓨터 방문 표시 배열 초기화
    
    // 네트워크의 개수를 카운트
    for (let i = 0 ; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
            answer++;
        }
    }
    
    function dfs(v) {
        visited[v] = true; // 방문 표시
        
        for (let nextV = 0; nextV < n; nextV++) {
            if (computers[v][nextV] && !visited[nextV]) { // 현재 컴퓨터와 연결되어 있으면서, 방문하지 않았을 경우
                dfs(nextV); 
            }
        }
    }
    
    
    return answer;
}