[JavaScript] 백준 코딩테스트 2606. 실버 3 : 바이러스

📌  문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

📌  입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

📌  출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

📌  예제 입출력

---

📌  풀이

알아야 하는 것

• DFS와 BFS
• 구조 분해 할당
• arr.filter / arr.map / arr.slice

구할 것

결론은 1번 노드랑 연결된 노드가 몇 개 있냐를 묻는 문제다.

1번 노드랑 연결된 노드를 찾는 문제니 dfs로 해야지 했는데 bfs로도 풀렸다.

이게 1번이랑 연결된 2번이 3번이랑도 연결되어 있으면 3번까지 포함하는 문제라서 연결된 너비를 찾는 것도 맞는 것 같다.

 

먼저 dfs로 풀었다.

input의 첫 줄에 노드의 수가 주어지고, 두 번째 줄에 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 

이를 numOfNode, numOfEdge로 받아 그래프를 구현한다. (모든 정보는 String이니 Number화 하는 것 잊지 말자...)

그래프를 구현할 때 간선의 정보는 input의 3번째 줄부터 주어진다.

따라서 i가 0일 때부터 input[i + 2]로 받아야 3번째 줄부터 가져올 수 있다. 

 

1번이랑 연결된 노드를 구하면서 그 노드들을 answer라는 배열에 넣어줬다.

어떤 게 연결됐냐고 묻는 게 아니라 연결된 컴퓨터의 개수를 묻는 문제니 배열의 길이를 return해준다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

// 노드 개수랑 간선 개수
const numOfNode = Number(input[0]);
const numOfEdge = Number(input[1]);

// 그래프 구현
const graph = Array.from(Array(numOfNode + 1), () => []);
for (let i = 0; i < numOfEdge; i++) {
  let [from, to] = input[i + 2].split(" ").map(Number);
  graph[from].push(to);
  graph[to].push(from);
}

// dfs 구현
function dfs(start, graph) {
  const answer = [];
  const stack = [];
  const visited = Array(numOfNode + 1).fill(false);

  stack.push(start);
  visited[start] = true;

  while (stack.length) {
    let node = stack.pop();

    for (let next of graph[node]) {
      if (!visited[next]) {
        stack.push(next);
        visited[next] = true;
        answer.push(next);
      }
    }
  }
  return answer.length;
}

console.log(dfs(1, graph));

 

bfs로 풀었다.

위 코드와 거의 똑같은데 bfs로 풀 때는 별도로 answer를 선언하지 않았다.

딱히 넣지 않아도 visited에 방문한 노드의 개수를 구하면 되기 때문이다.

visited에 방문했다 === 1번 노드와 이어져 연결됐다 라고 이해했기 때문에, visited = [false, true, true, true, false, true, true, false]로 나온다. 이 때 0번째 인덱스는 그래프를 만들 때부터 노드의 수 + 1 로 만들어서 빈 상태고, 1번째 인덱스는 1번부터 시작했으니 true로 방문 처리 하고 들어와서 그렇다. 따라서 0번, 1번 인덱스는 필요 없는 값이니 slice로 잘라낸 새로운 배열을 반환한다. 그리고 그 배열에서 값이 true인 것을 filter로 걸러낸 새 배열을 만들어 길이를 반환했다.

 

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const numOfNode = Number(input[0]);
const numOfEdge = Number(input[1]);

const graph = Array.from(Array(numOfNode + 1), () => []);
for (let i = 0; i < numOfEdge; i++) {
  let [from, to] = input[i + 2].split(" ").map(Number);
  graph[from].push(to);
  graph[to].push(from);
}

function bfs(start, graph) {
  const queue = [];
  const answer = [];
  const visited = Array(numOfNode + 1).fill(false);

  queue.push(start);
  visited[start] = true;

  while (queue.length) {
    let node = queue.shift();

    for (let next of graph[node]) {
      if (!visited[next]) {
        queue.push(next);
        visited[next] = true;
      }
    }
  }
  return visited;
}

console.log(
  bfs(1, graph)
    .slice(2)
    .filter((v) => v === true).length
);

 

백준 하다 보니 재밌는데!?