[백준] 1260번 DFS와 BFS (JavaScript)

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

1260번: DFS와 BFS

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

function bfs(graph, startNode) {
  const visited = [];
  let needVisit = [];

  needVisit.push(startNode);
  while (needVisit.length !== 0) {
    const node = needVisit.shift(); // 큐 구조로 shift 사용
    if (!visited.includes(node)) {
      visited.push(node);
      let nodes = graph[node];
      needVisit = [...needVisit, ...nodes.sort((a, b) => a - b)]; // 큐 구조 때문에 오름차 순
    }
  }
  return visited;
}

function dfs(graph, startNode) {
  const visited = [];
  let needVisit = [];

  needVisit.push(startNode);
  while (needVisit.length !== 0) {
    const node = needVisit.pop(); // 스택 구조로 pop사용
    if (!visited.includes(node)) {
      visited.push(node);
      let nodes = graph[node];
      needVisit = [...needVisit, ...nodes.sort((a, b) => b - a)]; // 스택때문에 내림차 순
    }
  }
  return visited;
}

let [n, m, v] = input.shift().split(" ").map(Number);
let graph = [...Array(n + 1)].map((e) => []);

for (let i = 0; i < m; i++) {
  let [start, end] = input[i].split(" ").map(Number);
  graph[start].push(end);
  graph[end].push(start);
}
console.log(dfs(graph, v).join(" "));
console.log(bfs(graph, v).join(" "));

 

간단한 인접 리스트 방식으로 푼 dfs와 bfs이다. 가장 기초이니 잘 알아둘것