🕊 Link

Lv3. 네트워크 Javascript
https://programmers.co.kr/learn/courses/30/lessons/43162

🧑🏻‍💻 Code(javascript)

function solution(n, coms) {
  const v = new Array(n).fill(false)
  const l = coms.length
  let count = 0
  const q = []

  for (let i = 0; i < l; i++) {
    if (!v[i]) {
      q.push(i)
      v[i] = true
      count++;
    }
    while (q.length) {
      const cur = q.shift()
      for (let j = 0; j < l; j++) {
        if (!v[j] && coms[cur][j]) {
          q.push(j)
          v[j] = true
        }
      }
    }
  }
  return count
}

💡 Solution

function solution(n, coms) {
  const v = new Array(n).fill(false) // visited
  const l = coms.length // for문 조건에서 coms.length를 쓰면 매번 계속해야하기 때문에 미리 선언
  let count = 0 // answer
  const q = [] // queue
  
  for (let i = 0; i < l; i++) { // 모든 node가 연결되어있지 않기 때문에 for문
    if (!v[i]) { // i를 방문한 적이 없다면
      q.push(i) // queue push
      v[i] = true // visited 방문 체크
      count++; // network count ++
      // 방문한 적이 없는 i를 queue에 넣으면서 count를 올려주고
      // 아래 while문에서 i를 시작으로 연결된 모든 node들을
      // queue에 push/shift 하며 visited 방문 체크를 할 것임
      // 따라서 count ++는 여기서만 하면 됨
    }
    while (q.length) { // queue에 요소가 남아 있으면 loop
      const cur = q.pop() // cur은 q의 가장 앞 요소(ex. cur = [1, 1, 0]) 
      // DFS는 BSF와 달리 이전의 노드가 아니라, 
      // 자기 자신과 연결되었던 노드들을 먼저 탐색하기 때문에 stack(push/pop)
      for (let j = 0; j < l; j++) { // cur의 요소를 돌면서 
        if (!v[j] && coms[cur][j]) { // 방문한 적이 없으면서 && cur에서 연결(1)된 경우
          q.push(j) // queue push
          v[j] = true // visited 방문 체크
        }
      }
    }
    // while문을 나온 순간 queue는 빈 배열일 것이고, 다시 i++을 하고 for문을 돈다.
    // 방문한 적이 있으면 visited가 true일 것이기 때문에 queue push가 일어나지 않음
    // 방문하지 않은 node만 찾아서 queue push / count++    
  }
  return count
}

🔁 복습 풀이

2021.09.01

function solution(n, coms) {
  let count = 0
  const visited = new Array(n).fill(0)
  for (let i = 0; i < n; i++) {
    if (visited[i] === 0) {
      count++
      visited[i] = 1
      dfs(coms, visited, i)
    }
  }
  return count
}

function dfs(coms, visited, i) {
  coms[i].forEach((item, j) => {
    if (i !== j && item !== 0 && visited[j] === 0) {
      visited[j] = 1
      dfs(coms, visited, j)
    }
  })
}

👨‍👦‍👦 Others

1. 프로그래머스 - 노영은 , sunny110님 => - 재귀를 활용한 DFS

let arr;
let visitArr;

function solution(n, computers) {
  let ctr = 0;
  arr = computers;
  visitArr = new Array(n).fill(false);

  for (let i in arr) {
    ctr += dfs(i);
  }

  return ctr;
}

function dfs(i) {
  if (visitArr[i] == true) return 0;
  else visitArr[i] = true;

  for (let j in arr[i]) {
    if (arr[i][j] == 1)
      dfs(j);
  }

  return 1;
}

2 : 프로그래머스 - -님

function solution(n, computers) {
    let answer = 0;
    const visitedNode = new Array(n).fill(false);

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

    for (let i = 0; i < n; i++) {
        if (!visitedNode[i]) {
            answer++;
            visitedNode[i] = true;
            fn(i);
        }
    }

    return answer;
}

3. 프로그래머스 : 구철회 , 김윤아님

function solution(n, computers) {
    var ret = 0;
    var visited = [];
    for(var i=0; i<n; i++) visited.push(false);
    for(var i=0; i<n; i++) {
        if(!visited[i]) {
            dfs(n, computers, i, visited);
            ret++;
        }
    }

    return ret;
}

function dfs(n, computers, cur, visited) {
    visited[cur] = true;

        for(var j=0; j<n; j++) {
            if(computers[cur][j] === 1 && !visited[j] && cur !== j) {
                visited[j] = true;
                dfs(n, computers, j, visited);
            }
        }

}

👨🏻‍💻💭 Self Feedback

• BSF/DSF를 이해하고나니 10분 내외로 해결

• 2021.08.11 - 최초 작성

댓글 환영 질문 환영
by.protect-me