[백준] 1260 DFS와 BFS - javascript

📌 문제

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

📌 풀이

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

let [n, m, v] = input[0].split(" ").map(Number);
let graph = new Array(n + 1);
for (let i = 0; i < graph.length; i++) {
  graph[i] = [];
}
for (let i = 0; i < m; i++) {
  let [from, to] = input[i + 1].split(" ").map(Number);
  graph[from].push(to);
  graph[to].push(from);
}
graph.forEach((element) => {
  element.sort((a, b) => a - b);
});
let visited = new Array(n + 1).fill(0);
let answer_dfs = [];
// DFS
function DFS(v) {
  if (visited[v]) return;
  visited[v] = 1;
  answer_dfs.push(v);
  for (let i = 0; i < graph[v].length; i++) {
    let next = graph[v][i];
    if (visited[next] === 0) {
      DFS(next);
    }
  }
}
DFS(v);
console.log(answer_dfs.join(" "));
// BFS
let answer_bfs = [];
visited.fill(0);
function BFS(v) {
  let queue = [v];
  while (queue.length) {
    let x = queue.shift();
    if (visited[x] === 1) {
      continue;
    }
    visited[x] = 1;
    answer_bfs.push(x);
    for (let i = 0; i < graph[x].length; i++) {
      let next = graph[x][i];
      if (visited[next] === 0) {
        queue.push(next);
      }
    }
  }
}
BFS(v);
console.log(answer_bfs.join(" "));

✔ 알고리즘 : DFS / BFS

✔ 간선의 정보를 입력받아 인접리스트를 통해 그래프로 구현

✔ 양방향 그래프이므로 a,b를 입력받으면 a,b각각 b,a를 추가해줘야함

✔ visited배열로 노드를 탐색했는지 안했는지 구별하고 DFS / BFS 탐색

✔ 방문한 순서대로 answer_dfs, answer_bfs에 저장 후 출력

❗ 문제 조건에 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고 라는 말이 있기 때문에 인접리스트로 그래프의 정보를 입력받고 정렬 후 탐색을 시작해야함

✔ 난이도 : 백준 기준 실버2