[Refresh ! 코딩 테스트 / js] 네트워크

문제 설명

• 그림에서 이어져 있는 노드들은 통일된 객체
• 이어지지 않는 노드들은 +1 씩 독립된 객체

나의 풀이

const solution = function (num,arr) {
  let map_sol= Array.from({length: arr.length},()=>[]);
    for(var i=0; i<arr.length; i++){
        for(var j=0; j<arr[i].length; j++){
            //i번 으로 들어가서 넣기 
            if(arr[i][j]==1){
                map_sol[i].push(j)
            }
        }
    }
    // 지금 자기 자신은 연결을 빼놨음
    
    const go_bfs= function(start){
        
        let visited=[];
        let stack=[start];
        // 시작하는 함수 
        while(stack.length>0){
            // 여기서 돌아간다. bfs 의 특징은 shift 으로 뽑고 push 으로 넣는다는거 
            var hey= stack.shift();
            map_sol[hey].map((el)=>{
                if(!visited.includes(el)){
                    //갔던게 아닌경우에는 
                    visited.push(el);
                    stack.push(el);
                    //을 하는데 이제 visted 에 넣었으면 다시 안가도 되는거잖아 
                    //근데 여기서 [] 을하면. 더못갈수도 있으니 마지막 visted 을 처리하는게 ..?
                }
            })
        }
        
        visited.map((el)=> map_sol[el]=[]);
    }
    let answer=0;
    
    for(var i=0; i<map_sol.length; i++){
        
        // 여기서 bfs 을 가면서 map_sol 을 컨트롤 하는 함수를 만든다고 생각
        if(map_sol[i].length>1){
            go_bfs(i)   
            answer+=1;
        }
        if(map_sol[i].length==1){
            answer+=1;
        }
      
    }
    // 이래도 결과는 똑같이 나온다.
    return answer;
    
 
}

• arr을 이용해서 연결된거 끼리 하나로 친다.
• !! 만약 연결된게 다시 start가 된다면. 시간 오류 발생 > 따라서 하나의 객체 안에 visted 가 된 노드가 있다면 이 노드는 start하면 안됨
• 따라서 visted 된 노드들을 map 으로 체크하면서 원래 arr 의 형태를 [] 으로 바꿔줌
• 독립된 객체들은 +1 씩 count 함

다른 사람 풀이

function solution(n, computers) {
    let answer = 0;
    const visited = [];
    
    for(let i = 0; i < n; i++) {
        if(!visited[i]) {
            dfs(i, visited, computers);	// 방문하지 않은 노드에서 dfs 탐색
            answer++;	// 해당 시점에서는 위의 조건문으로 이미 위에 dfs 탐색에서 방문된 노드는 더 이상 방문하지 않는 것이 보장됨
            		// 따라서 그냥 방문 후 개수 count 해도 중복 발생 X
        }
    }
    
    return answer;
}

const dfs = (node, visited, computers) => {
    visited[node] = true;	// 현재 node를 방문처리 하고
    for(let i = 0; i < computers.length; i++) {
        if(computers[node][i] === 1 && !visited[i]) 	// 연결된 노드가 있고 해당 노드를 방문하지 않았다면
            dfs(i, visited, computers);		// dfs로 방문 진행
    }
}

내코드와 비교

• ( 다른 사람 코드를 보니 내 코드가 정말.. 더럽고 간편하지 못한 코드였구나 싶었다.. 😬😬😬😬 )
• 처음부터 map 으로 만들지 말고 주어진 computer 을 이용
• for문으로 dfs 의 시작을 열고 vistted 를 밖으로 빼서 관리함
• dfs 문에서 visted 을 관리해서 빠르게 품