[콭] 네트워크 BFS/DFS

코딩테스트 연습
깊이/너비 우선 탐색(DFS/BFS)
네트워크

문제

상호 간 네트워크로 연결된 컴퓨터가 있다. 네트워크 연결에 대한 정보가 담긴 배열을 통해 네트워크의 개수를 구하라.

로직

1. 반복문을 통해 노드에 방문
2. 노드에 방문표시를 하고 연결된 노드(방문하지 않았던)에 방문

DFS를 이용한 javascript 코드

function solution(n, computers) {
    var answer = 0;
    let visited=[];
    for(let i=0;i<n;i++){
        visited[i]=false;
    }
    
    const DFS=(idx)=>{
        visited[idx]=true;
        for(let i=0;i<n;i++){
            if(computers[idx][i]&&!visited[i]) DFS(i);
        }
    }
    
    for(let i=0;i<n;i++){
        if(!visited[i]){
            DFS(i);
            answer++;
        }
    }
    
    return answer;
}

BFS를 이용한 javascript 코드

function solution(n, computers) {
  let answer = 0;
  let visit = [];
  let needVisit = [];

  for (let i = 0; i < n; i++) {
    visit.push(false);
  }

  for (let i = 0; i < n; i++) {
    if (visit[i]) continue;

    //방문하지 않은 노드들
    needVisit.push(i);
    visit[i] = true;

    while (needVisit.length) {
      let node = needVisit.shift();
      computers[node].forEach((e, idx) => {
        if (idx !== node) {//다른 노드라면
          if (!visit[idx] && computers[node][idx]) {//해당 노드를 방문x,연결 o
            visit[idx] = true;
            needVisit.push(idx);//방문할 노드에 추가
          }
        }
      });
    }
    
    answer++;
  }

  return answer;
}

23.04.03 다시 풀기

복잡하게 풀어서 방문할 노드와 방문한 노드로 둘 다 구분하여 표현하는 게 좋겠다.

방문 표시 : 0,1=>num

function solution(n, computers) {
  
  let visit = [];
  let num = 2;//1과 구분하기 위해 2로 설정
  
  for (let i = 0; i < n; i++) {
    visit.push([i, computers[i]]); 
    
    if (computers[i][i] !== 1) continue; //방문한 노드면 통과
    
    while (visit.length) {
      let [me, cArr] = visit.shift();
      for (let j = 0; j < n; j++) {
         
        if (computers[j][j] !== 1||cArr[j] === 0) continue;//방문한 노드 또는 연결x면 통과  
        
        if (j === me) continue;//같은 컴퓨터는 통과
        
        visit.push([j, computers[j]]);
        
        //자신을 가리키는 자리에 num 저장, 만약 저장되어 있다면 num 소환
        if (computers[j][j] === 1) computers[j][j] = num;
        else num = computers[j][j];
      }
      computers[i][i] = num; 
    }
    num += 1; 
  } 
  return num - 2;
}