[JavaScript] 네트워크

level : 3
문제 링크 : 네트워크

프로그래머스

My Solution

function solution(n, computers) {
    let answer = 0;
    /// visited matrix로 방문 여부 판단
    let visited = new Array(n).fill(false);
    for(let i = 0; i < n; i++){
        if(!visited[i]){
            dfs(i,n,computers,visited);
            answer++;
        }
    }
    return answer;
}
function dfs(start,n,matrix,visited){
    visited[start] = true;
    let temp = [];
    for(let i = 0; i < n; i++){
        if(i!==start&&matrix[start][i]===1&&!visited[i])
            temp.push(i);
    }
    temp.forEach((value)=>{
        dfs(value,n,matrix,visited);
    })
}

풀이방법
위의 문제는 그래프 문제이며 dfs와 bfs 두 방법으로 모두 풀 수 있는 문제이다.
dfs와 bfs 어느 방법으로 풀어도 시간복잡도를 줄일 수는 없다고 생각이 들었다.

그리하여 유지보수가 용이하도록 함수를 따로 만들어 사용하는 dfs를 선택하였다.
문제에서는 그래프 이론을 이용하기 위하여 2차원 배열을 사용하였지만 실제로 판별하기 위해서는 2차원 배열까지는 필요 없었다.
방문 여부를 판단하기 위하여 visited라는 길이가 n인 1차원 array를 만들고 모든 값을 false로 초기화 한다.

0부터 n-1까지의 숫자를 탐색하며 방문하지 않읐으면 dfs라는 함수에 넣어 깊이 우선 탐색을 진행한다.
dfs의 파라미터로는 판별할 컴퓨터의 index, 컴퓨터의 최대갯수, 관계를 나타내 주는 matrix, 방문 여부 array를 갖는다.
(사실 컴퓨터의 최대갯수는 계산량을 줄이기 위하여 넣었다. 개인적으로 JavaScript는 파라미터로 array를 넘기면 call-by-reference로 넘어가서 c++에서 포인터를 쓰는 형식보다 편하긴하다.)
dfs함수가 모두 끝나면 answer를 1 증가 시킨다.

마지막으로 answer를 반환한다.

풀이방법의 시간 복잡도는 O(N^2)이다.

느낀점
시간 복잡도를 O(N^2)보다 줄이려고 했으나 더는 좋은 방법이 떠오르지는 않았기에 그냥 풀었다.
더 좋은 방법은 없어 보인다.