[백준] DFS와 BFS

문제 설명

가중치가 없는 그래프 탐색 문제다. 노드, 간선정보, 시작 노드 정보가 주어졌을 때 DFS와 BFS의 경로를 찍는 문제다.

문제 풀이

DFS와 BFS를 사용했을 때 탐색 경로를 정확하게 이해하고 있었다면 쉽게 풀 수 있었을텐데 습관적으로 풀던 방식을 암기해서 풀다보니 시간이 오래걸렸다. 우선 경로를 찍어주는 부분을 어떻게 해줘야 할지 몰라서 헤맸는데 체크 배열을 만들고 한번 방문한 곳은 다시는 방문하지 않는 방식으로 탐색하도록 했다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [NMT, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M, V] = NMT.split(" ").map(Number);
const arr = input.map((v) => v.split(" ").map(Number));
const g = Array.from({ length: N + 1 }, () => Array(N + 1).fill(0));
const check1 = Array(N + 1).fill(false);
const dfsPath = [];
arr.forEach(([a, b]) => {
  g[a][b] = 1;
  g[b][a] = 1;
});
const dfs = (v) => {
  dfsPath.push(v);
  for (let i = 0; i < g[v].length; i++) {
    if (g[v][i] === 1 && !check1[i]) {
      check1[i] = true;
      dfs(i);
    }
  }
};
check1[V] = true;
dfs(V);

const bfsPath = [];
const check2 = Array(N + 1).fill(false);
const queue = [[V, `${V}`]];
check2[V] = true;
while (queue.length > 0) {
  const [current, path] = queue.shift();
  bfsPath.push(current);
  for (let i = 0; i < g[current].length; i++) {
    if (g[current][i] === 1 && !check2[i]) {
      check2[i] = true;
      queue.push([i, path + `${i}`]);
    }
  }
}

console.log(dfsPath.join(" "));
console.log(bfsPath.join(" "));

출처: 백준 - DFS와 BFS https://www.acmicpc.net/problem/1260