네트워크 javascript - 프로그래머스

문제이해

간단한 DFS/BFS 문제입니다.

DFS,BFS의 목적은 모든 노드를 한 번씩 방문하는 것입니다.

방문을 한 번씩 하려면 방문 했는지 기록해놔야합니다.

방문 했음을 기록할 check 배열을 노드의 개수만큼 만듭니다.

로직

i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computer[i][j]를 1로 표현해놨음.

일단 모든 컴퓨터에서 DFS로 노드를 방문할 로직을 수행합니다.

DFS 내부로직에서는 현재 노드를 방문했다는 기록을 하고, 현재 노드에서 연결된 노드를 살펴보며 이전에 방문했는지를 체크배열로 확인하며, 연결된 노드이며 아직 방문 하지 않았으면 DFS를 재귀호출합니다.
연결된 노드들은 한번의 DFS로 모두 방문 할 수 있습니다.

연결된 노드들을 네트워크라 치면, DFS로직 밖에서 DFS호출한 회수로 네트워크 개수를 구할 수 있습니다.

code

function solution(n, computers) {
    var answer = 0;
    
    const check = [];
    for(const computer of computers){
        check.push(false);
    }
        
    function DFS(index){
        check[index] = true;
        
        for(let i = 0; i< computers.length; i++ ){
            if(computers[index][i] === 1 && !check[i]){
                DFS(i);
            }
        }
    }
    
    for(let  i = 0;  i < computers.length; i++ ){
        if(!check[i]){
            DFS(i);
            answer+=1;
        }
    }
        
    return answer;
}