[백준 1260 - Node.js] DFS와 BFS

🔗 문제 링크

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

1260번: DFS와 BFS

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M, V] = input.shift().split(' ').map(Number);
const edges = input.map(v => v.split(' ').map(Number));
const graph = [...Array(N + 1)].map(() => []);
edges.forEach(([from, to]) => {
  graph[from].push(to);
  graph[to].push(from);
});

const dfs = (start) => {
  const stack = [start];
  const visited = Array(N + 1).fill(false);
  const order = [];
  while (stack.length) {
    const node = stack.pop();
    if (!visited[node]) {
      visited[node] = true;
      order.push(node);
      stack.push(...graph[node]);
    }
  }
  return order.join(' ');
};

const bfs = (start) => {
  const queue = [start];
  const visited = Array(N + 1).fill(false);
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    if (!visited[node]) {
      visited[node] = true;
      order.push(node);
      queue.push(...graph[node]);
    }
  }
  return order.join(' ');
};

graph.forEach(v => v.sort((a, b) => b - a));
console.log(dfs(V));

graph.forEach(v => v.sort((a, b) => a - b));
console.log(bfs(V));

DFS는 stack을 이용하기 때문에 stack의 뒤에서부터 탐색을 한다는 점을 이용하여 graph의 모든 인접 노드들을 내림차순 정렬한 후에 DFS를 실행하였다.

BFS의 경우는 queue를 이용하기 때문에 앞에서부터 정방향으로 탐색하므로, graph의 모든 인접 노드들을 오름차순 정렬한 후에 BFS를 실행하였다.

 

 

🗃️ 다른 언어로 된 풀이

[백준 1260] DFS와 BFS with Python