[백준] 2606. 바이러스 (자바스크립트/javascript/node.js/BFS/DFS/너비 우선 탐색 / 깊이 우선 탐색 / 알고리즘 / 코딩테스트)

---

 

문제를 풀기 위한 아이디어

1번 컴퓨터부터 시작하여 경로를 거치게 되는 정점을 모두 구하는 문제이다.

DFS 방법으로 풀어도 되고 BFS 방법으로 풀어도 무방하다.

예제의 경우 DFS로 풀면 1→2→3→5→6 순으로 거치게 되고, BFS로 풀면 1→2→5→3→6 으로 거치게 된다.

 

---

내가 작성한 코드 

 

1. DFS로 푼 방법

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
const vertexNumber = Number(input[0]); // 컴퓨터의 수 : 7
const edgeNumber = Number(input[1]); // 간선의 수 : 6
input.shift();
input.shift();

class UndirectedGraph {
  constructor() {
    this.edges = {};
    this.DFSArray = [];
  }

  // 정점 추가하기
  addVertex(vertex) {
    this.edges[vertex] = {};
  }

  // 간선 추가하기
  addEdges(vertex1, vertex2) {
    this.edges[vertex1][vertex2] = true;
    this.edges[vertex2][vertex1] = true;
  }

  // DFS
  traverseDFS(vertex) {
    const visited = {};
    this._traverseDFS(vertex, visited);
    return this.DFSArray;
  }
  _traverseDFS(vertex, visited) {
    visited[vertex] = true;
    this.DFSArray.push(vertex);

    for (let adjacentVertex in this.edges[vertex]) {
      if (!visited[adjacentVertex]) {
        this._traverseDFS(adjacentVertex, visited);
      }
    }
  }
}

const undirectedGraph = new UndirectedGraph();
for (let i = 1; i <= vertexNumber; i++) {
  undirectedGraph.addVertex(Number(i));
}
for (let j = 0; j < edgeNumber; j++) {
  input[j] = input[j].split(" ");
  undirectedGraph.addEdges(Number(input[j][0]), Number(input[j][1]));
}

const answer = undirectedGraph.traverseDFS(1).length - 1;
console.log(answer);

 

2. BFS로 푼 방법

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
const vertexNumber = Number(input[0]); // 컴퓨터의 수 : 7
const edgeNumber = Number(input[1]); // 간선의 수 : 6
input.shift();
input.shift();

class UndirectedGraph {
  constructor() {
    this.edges = {};
    this.BFSArray = [];
  }

  // 정점 추가하기
  addVertex(vertex) {
    this.edges[vertex] = {};
  }

  // 간선 추가하기
  addEdges(vertex1, vertex2) {
    this.edges[vertex1][vertex2] = true;
    this.edges[vertex2][vertex1] = true;
  }

  // BFS
  traverseBFS(vertex) {
    const queue = [];
    const visited = {};
    queue.push(vertex);

    while (queue.length) {
      vertex = queue.shift();
      if (!visited[vertex]) {
        visited[vertex] = true;
        this.BFSArray.push(vertex);
        for (let adjacentVertex in this.edges[vertex]) {
          queue.push(adjacentVertex);
        }
      }
    }
    return this.BFSArray;
  }
}

const undirectedGraph = new UndirectedGraph();
for (let i = 1; i <= vertexNumber; i++) {
  undirectedGraph.addVertex(i);
}

for (let j = 0; j < edgeNumber; j++) {
  input[j] = input[j].split(" ");
  undirectedGraph.addEdges(Number(input[j][0]), Number(input[j][1]));
}
const answer = undirectedGraph.traverseBFS(1).length - 1;
console.log(answer);