[ 자바스크립트(JavaScript) ] 프로그래머스 level3 - 네트워크

📍 프로그래머스 3단계 - 네트워크

프로그래머스 3단계 - 네트워크

 

이 문제를 그래프의 개념을 알고 있어야 풀 수 있는 문제이기 때문에 조금 까다로울 수 있다. 결론적으로 visited 배열을 선언하여 노드 방문 여부를 체크해주면 된다. 4번째 줄에 반복문을 사용한 이유는 모든 노드를 한 번씩 탐색하기 위함이다. 만약, 모든 노드가 서로 연결되어있지 않다면 갈 수 없기 때문이다. 이때, 이전에 방문한 노드는 탐색하지 않도록 조건문을 넣어줬다.

 

DFS 함수에서는 node와 연결된 다른 node를 방문하는 로직인데, 현재 노드에서 visited배열로 방문 체크해주고, 다음 노드와 연결되어있다면(computers[node][i]) 해당 노드로 이동하는데 이때 주의할 점은 방문하지 않은 노드여야 한다는 점이다. 여기서도 반복문을 사용한 이유는 computers[node]모든 노드를 탐색하기 위함이다.

728x90

function solution(n, computers) {
    const visited = Array.from({length: n}, () => 0);
    let answer = 0;

    for (let i=0; i<n; i++){
        if(!visited[i]){
            DFS(i);
            answer++;
        }
    }

    function DFS(node){
        visited[node] = 1;
        for(let i=0; i<n; i++){
            if(computers[node][i] && !visited[i]){
                DFS(i)
            }
        }
    }

    return answer;
}