[백준 1260번] DFS와 BFS - 자바스크립트(nodejs)

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

1260번: DFS와 BFS

const { off } = require('process');
const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

class Graph {
  constructor() {
    this.node = {};
  }

  addVertex(vertex) {
    if (!this.node[vertex]) {
      this.node[vertex] = [];
    }
  }

  addEdge(v1, v2) {
    this.node[v1].push(v2);
    this.node[v2].push(v1);
  }

  depthFirstSearch(start) {
    const result = [];
    const visited = {};
    const node = this.node;

    function dfs(vertex) {
      if (!vertex) return;
      result.push(vertex);
      visited[vertex] = true;
      node[vertex]
        .sort((a, b) => a - b)
        .forEach((v) => {
          if (!visited[v]) {
            visited[v] = true;

            return dfs(v);
          }
        });
    }

    dfs(start);
    return result;
  }

  breadthFirstSearch(start) {
    const queue = [start];
    const result = [];
    const visited = {};

    visited[start] = true;

    while (queue.length) {
      const value = queue.shift();
      result.push(value);
      this.node[value]
        .sort((a, b) => a - b)
        .forEach((v) => {
          if (!visited[v]) {
            visited[v] = true;
            queue.push(v);
          }
        });
    }
    return result;
  }
}

let input = [];

rl.on('line', function (line) {
  input.push(line);
  if (input.length === +input[0].split(' ')[1] + 1) {
    rl.close();
  }
}).on('close', function () {
  const [num, ver, start] = input.shift().split(' ');
  const vertex = input.map((v) => v.split(' ').map(Number));

  const graph = new Graph();

  for (let i = 1; i <= +num; i++) {
    graph.addVertex(i);
  }

  vertex.sort((a, b) => a[0] - b[0]);

  vertex.forEach((v) => {
    graph.addEdge(v[0], v[1]);
  });
  console.log(graph.depthFirstSearch(start).join(' '));
  console.log(graph.breadthFirstSearch(start).join(' '));
});

중요한 건 제시된 간선들을 정렬하고, 간선을 넣은 객체 내부에서도 오름차순으로 정렬된 상태여야 된다!

(아니면 예제가 맞고, 질문하기에 있는 반례가 맞든 계속 틀립니다.)

 

우선 간선을 숫자별로 정렬해서 값에 넣어준다.

 

Graph {
  node: {
    '1': [ 2, 3 ],
    '2': [ 1, 5 ],
    '3': [ 4, 1 ],
    '4': [ 3, 5 ],
    '5': [ 4, 2 ]
  }
}

 

그리고 bfs, dfs를 순회할 때 해당 간선들의 배열을 오름차순으로 sort해주면서 하면 된다.