duck blog
Published on

프로그래머스 네트워크 (bfs/dfs)

Authors
  • avatar
    Name
    Deokgoo Kim
    Twitter

문제 풀이

bfs/dfs 분류의 문제입니다. 코멘트에서도 언급하지만
테스트케이스에 비대칭으로 주어지는것 같습니다.
난이도는 낮다고 생각합니다.

function solution(n, computers) {
  let answer = 0;
  let networkMap = new Array(n);

  // 주어진 computers를 대칭적으로 만듭니다.
  for(let y=0;y<n;y++) {
    for(let x=0;x<n;x++) {
      if(computers[y][x] || computers[x][y]) {
        computers[y][x] = 1;
        computers[x][y] = 1;
      }
    }
  }

  const dfs = (target) => {
    networkMap[target] = 1;
    for(let z=0;z<n;z++) {
      if(target === z) continue;
      if(computers[target][z] && !networkMap[z]) {
        dfs(z);
      }
    }
  }

  for(let i=0;i<n;i++) {
    if(networkMap[i]) continue;
    answer++;
    dfs(i);
  }

  return answer;
}