DFS와 BFS

문제 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 > 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

문제 풀이

1. excuteDFS
   1. 방문 확인을 위해 visited배열 선언(+1을 해줘서 정점과 배열 인덱스를 맞춰서 사용.)
   2. dfs는 스택을 사용해서 구현.
   3. 방문안한 정점이라면 dfs에 push.
   4. startEdge를 방문했다고 바꿔줌.
   5. edges를 살펴보면서, 양방향이니까 edge[0],edge[1]에서 연결된 정점을 찾음.
   6. 번호가 작은 순서기 때문에 정렬(내림차).
   7. stack에 다시 넣어줌.
2. excuteBFS
   1. 위의 과정에서 pop() 대신 shift()를 사용, 정렬은 오름차순.

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

const [vertexsLength, _, START] = input[0]
  .trim()
  .split(" ")
  .map(element => Number(element));

const getEdges = input => {
  const edges = [];
  input.forEach(edge => {
    const [start, end] = edge.split(" ").map(element => Number(element));
    edges.push([start, end]);
  });
  return edges;
};

const excuteDFS = (edges, start, vertexsLength) => {
  const visited = Array(vertexsLength + 1).fill(false);
  const stack = [start];
  const dfs = [];
  while (stack.length !== 0) {
    let startEdge = stack.pop();
    if (!visited[startEdge]) dfs.push(startEdge);
    visited[startEdge] = true;
    let connectEdges = [];
    edges.forEach(edge => {
      if (edge[0] === startEdge && !visited[edge[1]]) {
        connectEdges.push(edge[1]);
      } else if (edge[1] === startEdge && !visited[edge[0]]) {
        connectEdges.push(edge[0]);
      }
    });
    connectEdges.sort((a, b) => b - a);
    stack.push(...connectEdges);
  }
  return dfs;
};

const excuteBFS = (edges, start, vertexsLength) => {
  const visited = Array(vertexsLength + 1).fill(false);
  const queue = [start];
  const bfs = [];
  while (queue.length !== 0) {
    let startEdge = queue.shift();
    if (!visited[startEdge]) bfs.push(startEdge);
    visited[startEdge] = true;
    let connectEdges = [];
    edges.forEach(edge => {
      if (edge[0] === startEdge && !visited[edge[1]]) {
        connectEdges.push(edge[1]);
      } else if (edge[1] === startEdge && !visited[edge[0]]) {
        connectEdges.push(edge[0]);
      }
    });
    connectEdges.sort((a, b) => a - b);
    queue.push(...connectEdges);
  }
  return bfs;
};

const print = result => {
  let resultString = "";
  result.forEach(element => {
    resultString += `${element} `;
  });
  console.log(resultString);
};

const edges = getEdges(input.slice(1, input.length));
const resultDFS = excuteDFS(edges, START, vertexsLength);
const resultBFS = excuteBFS(edges, START, vertexsLength);

print(resultDFS);
print(resultBFS);