[Baekjoon (Node.js)] 2606번 바이러스

📄 문제

문제 사진

 

입출력 예제

---

😅 나의 실패 풀이

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((item) => item.replace("\r", "").split(" "));

let result = 0;
const N = input.shift()[0];
const edge = input.shift()[0];
class Graph {
  constructor() {
    this.nodes = {};
  }

  addNode(node) {
    this.nodes[node] = {} || [];
  }

  addEdge(fromNode, toNode) {
    this.nodes[fromNode][toNode] = true;
    this.nodes[toNode][fromNode] = true;
  }

  BFS(fromNode) {
    let queue = [];
    let visited = {};

    queue.push(fromNode);

    while (queue.length) {
      fromNode = queue.shift();
      if (!visited[fromNode]) {
        visited[fromNode] = true;
        result++;
        for (let addNode in this.nodes[fromNode]) {
          queue.push(addNode);
        }
      }
    }
  }
}

const seokhoGraph = new Graph();

for (let i = 1; i <= N; i++) {
  seokhoGraph.addNode(i);
}

for (let i = 0; i < edge; i++) {
  let target = input[i];
  let [from, to] = target;
  seokhoGraph.addEdge(from, to);
}
seokhoGraph.BFS("1");

console.log(count - 1);

 

바로 런타임 에러 ㅜㅜ

---

😂 실패 풀이 접근법 

1. BFS를 돌려서 컴퓨터가 감염 될 때마다 +1 씩 해 줄 result를 선언한다.

2. 입력을 쪼개서 컴퓨터의 수, 연결되어 있는 쌍을 저장한다.

3. class 문법으로 graph를 만든다. (원래는 prototype을 쓰다가 팀원 'BOB' 덕분에 class의 세계로 왔다.)

4. 정점 추가, 간선 추가, BFS 함수를 안에다 만든다.

5. BFS를 돌리면 1과 이어져 있는 컴퓨터들의 개수만큼 result 에 숫자가 잘 들어간다!

6. 1번 컴퓨터는 제외해야 하니까 result - 1을 출력한다.

 

결과는?  런타임 에러

---

🤔 왜 그럴까?

- 처음엔 감을 못잡았다. 복잡한 루프도 없고, 이 문제의 fs 모듈 속도 이슈도 없는데...

- 그러다가 전역으로 잡은 result가 보여서 result 를 class 안에 배열로 새로 넣었다.

- BFS 로직에 reuslt++ 한 줄을 this.result.push(fromnode)로 바꿔서 클래스 안에서만 놀게 했다.

 

결과는? 구현 성공!

---

📝 나의 통과 풀이

const input = require("fs")
  .readFileSync("./pb.txt")
  .toString()
  .trim()
  .split("\n")
  .map((item) => item.replace("\r", "").split(" "));

const N = input.shift()[0];
const edge = input.shift()[0];
class Graph {
  constructor() {
    this.nodes = {};
    this.result = [];
  }

  addNode(node) {
    this.nodes[node] = {} || [];
  }

  addEdge(fromNode, toNode) {
    this.nodes[fromNode][toNode] = true;
    this.nodes[toNode][fromNode] = true;
  }

  BFS(fromNode) {
    let queue = [];
    let visited = {};

    queue.push(fromNode);

    while (queue.length) {
      fromNode = queue.shift();
      if (!visited[fromNode]) {
        visited[fromNode] = true;
        this.result.push(fromNode);
        for (let addNode in this.nodes[fromNode]) {
          queue.push(addNode);
        }
      }
    }
    return this.result;
  }
}

const seokhoGraph = new Graph();

for (let i = 1; i <= N; i++) {
  seokhoGraph.addNode(i);
}

for (let i = 0; i < edge; i++) {
  let target = input[i];
  let [from, to] = target;
  seokhoGraph.addEdge(from, to);
}

console.log(seokhoGraph.BFS("1").length - 1);

성공!

---

⌨ 접근법

1 실패 접근법에서 result 를 카운트 하는 bfs를 => result 객체를 가공하고 return 하는 로직으로 바꾼다.

2. return 된 result 객체의 개수에서 -1 을 해서 출력한다!

---

📚 문제 링크

https://www.acmicpc.net/problem/2606

2606번: 바이러스