43162. 네트워크

프로그래머스 43162번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 네트워크 | 프로그래머스 스쿨

풀이

아이디어

BFS를 느끼자… 이번 네트워크나 백준의 토마토 문제처럼 어떤 지점을 기준으로 연결된 점을 통해서 영역을 넓혀가는 느낌은 bfs를 먼저 떠올리면 된다.

이 문제 역시 어떤 컴퓨터를 기준으로 인접한 컴퓨터들을 타고 타고 가서 연결될 수 있는 가장 넓은 영역을 구하는 작업이 필요하고, 이건 bfs를 이용하면 간단히 해결할 수 있다.

그리고 그 영역들의 개수를 구해야 하므로 영역에 포함된 컴퓨터들을 방문 표시해두면서 새로운 영역들을 계속 찾아가면 (bfs를 수행) 답을 구할 수 있다.

이게 왜 Level 3 문제일까… 인접행렬이 주어져서 그런가?

코드

function solution(n, computers) {
  let answer = 0;
  const visited = new Uint8Array(n);

  function bfs(start) {
    const queue = [start];
    let head = 0;
    visited[start] = 1;

    while (head < queue.length) {
      const cur = queue[head++];

      for (let next = 0; next < n; next++) {
        if (computers[cur][next] === 0) continue;
        if (visited[next]) continue;

        visited[next] = 1;
        queue.push(next);
      }
    }
  }

  for (let start = 0; start < n; start++) {
    // 이미 어떤 네트워크에 속해 있는 경우는 제외한다.
    if (visited[start]) continue;
    bfs(start);
    answer++; // bfs 1번 = 네트워크 하나.
  }
  return answer;
}