[프로그래머스 lev3/JS] 네트워크

문제 출처

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

나의 풀이

computers 배열 자체가 연결 정보를 의미하므로
별도로 그래프를 생성할 필요도 없는 문제이다.

판단 기준은 방문했는지 여부로 잡는다.

for문을 돌면서 각 index에서 방문하지 않았다면 ++해준다.
동시에 dfs를 실행해서 연결된 지점을 모두 방문으로 체크해준다(dfs, 깊이우선탐색).

이미 방문했다면 다른 노드와 연결되었다는 의미이므로 ++하지 않는다.

function solution(n, computers) {
  let visited = [false];
  let answer = 0;

  const dfs = (i) => {
    visited[i] = true;
    for(let j=0; j<computers[i].length; j++) {
      if(computers[i][j]===1 && !visited[j]){
        dfs(j);
      }
    }
  }
  
  for (let i=0; i < computers.length; i++) {
    if (!visited[i]) {
      dfs(i)
      answer++;
    }
  }
  return answer;
}

console.log(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]))
// console.log(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))

다른 풀이

index(또는 key)를 활용하고 싶으면 for ...in
value를 활용하고 싶으면 for ...of (Iterable objects만 사용 가능)

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

  const dfs = (idx) => {
    if(visited[idx]) return 0
    
    visited[idx] = true

    for(let j in computers[idx]) {
      if(computers[idx][j] === 1) {
        dfs(j)
      }
    }
    return 1
  }

  for(let i in computers){
    answer += dfs(i)
  }

  return answer
}

다른 풀이 (bfs)

function solution(n, computers) {
  var answer = 0;
  let vis=Array(n).fill(0);
  
  for(let i=0; i<computers.length; i++){
    if(!vis[i]){
      vis[i]=1;
      let q=[i];
      while(q.length>0){
        let cur=q.shift();
        for(let j=0; j<computers[cur].length; j++){
          if(computers[cur][j]===1 && !vis[j]){
            vis[j]=1;
            q.push(j);
          }
      	}
      }   
      answer++;
    }
  }
  
  return answer;
}