[Javascript/자바스크립트] 백준 1260번 DFS와 BFS

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

 

코드

const dfs = (visit_num, visited, now, graph) => {
  if (visit_num == graph.length) {
    return;
  }
  dfs_path.push(now); // 현재 방문 노드
  visited[now] = true;
  for (const nx of graph[now]) {
    if (!visited[nx]) {
      dfs(visit_num + 1, visited, nx, graph);
    }
  }
};

const bfs = (n, graph, start) => {
  let q = [start];
  let visited = new Array(n + 1).fill(false);
  visited[start] = true;

  let bfs_path = [start];

  while (q.length > 0) {
    now = q.shift();
    for (const nx of graph[now]) {
      if (!visited[nx]) {
        q.push(nx);
        visited[nx] = true;
        bfs_path.push(nx);
      }
    }
  }
  return bfs_path;
};

const fs = require("fs");
const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m, v] = input[0].split(" ").map((num) => +num);
// 간선 연결 정보
const graph = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i < m + 1; i++) {
  const [a, b] = input[i].split(" ").map((num) => +num);
  graph[a].push(b);
  graph[b].push(a);
}
// 간선 연결 정보 정렬
graph.forEach((e) => e.sort((a, b) => a - b));

// DFS
let visited = new Array(n + 1).fill(false);
dfs_path = [];
dfs(1, visited, v, graph, dfs_path);
// BFS
let bfs_path = bfs(n, graph, v);

console.log(dfs_path.join(" "));
console.log(bfs_path.join(" "));

 

자바스크립트로 하려니까 DFS, BFS도 어렵다...

DFS와 BFS 모두 노드를 방문할 때마다 출력하도록 하려고 했는데, console.log()는 출력을 할 때마다 개행을 하기 때문에 줄 바꿈이 없이 출력하려면 process.stdout.write()로 출력해야 한다고 한다. 그렇지만 이런 출력 함수가 많이 실행되면 속도에 영향을 미친다고 하여 그냥 경로를 array에 모두 저장해둔 뒤에 한 번에 출력하는 방식으로 바꿨다.

 

❗ 더 공부해야할 점

1. 배열 생성 및 초기화

2. 배열 정렬

3. for문