[C3] 1260 - DFS와 BFS

 

문제

풀이

DFS는 재귀로, BFS는 큐를 이용해서 풀었다.

먼저 노드 정보를 이용해 그래프를 만들어준다.

그래프는 객체로 만들어도 되고, 이차원 배열로 만들어도 되는데 나는 일단 이차원 배열을 사용하고 있다.

노드가 n개, 간선이 m개이므로 그래프는 n개의 요소를 가진 이차원 배열이고, n번 노드와 연결된 노드들을 n-1번 배열에 넣어주면 된다.

편의를 위해 n이 아니라 n+1개의 배열을 만들어주고, 0번 배열은 비워 1번부터 시작하도록 해주면 좋다

노드	연결된 노드
0	-
1	2, 3
2	1, 4
3	1, 4
4	1,2,3

 

const graph = Array.from({ length: n + 1 }, () => []);
  input.forEach((el) => {
    const [s, e] = el;
    graph[s].push(e);
    graph[e].push(s);
  });

 

먼저 DFS를 살펴보자

DFS는 시작 노드의 인접 노드를 탐색하고, 해당 인접 노드의 인접 노드를 탐색, 또 인접 노드를 탐색....하는 과정을 거친다

방문하지 않은 인접 노드를 방문하고, 한번 방문한 노드는 다시 방문하지 않도록 방문 처리를 해준다.

인접 노드로 이동했다면, 해당 노드를 방문 배열에 넣고 인접 노드를 탐색하도록 한다.

만약 현재 노드를 이미 방문했다면 재귀를 종료시킨다.

const dfsCheck = Array(n + 1).fill(false);
  const dfsAns = [];
  const dfs = (curNode) => {
    if (dfsCheck[curNode]) return;
    dfsCheck[curNode] = true;
    dfsAns.push(curNode);
    for (let next of graph[curNode]) {
      if (!dfsCheck[next]) {
        dfs(next);
      }
    }
  };

 

BFS는 한 노드의 인접 노드들을 모두 탐색하는 과정을 거친다

시작 노드의 인접 노드들을 모두 방문하고, 큐에 넣어준다

반복문을 거치며 모든 노드들을 탐색했다면 반복을 종료한다.

const bfsCheck = Array(n + 1).fill(false);
  const bfsAns = [];
  const bfs = () => {
    const queue = [v];

    while (queue.length > 0) {
      const curNode = queue.shift();
      if (bfsCheck[curNode]) continue;
      bfsCheck[curNode] = true;
      bfsAns.push(curNode);

      for (let next of graph[curNode]) {
        if (!bfsCheck[next]) {
          queue.push(next);
        }
      }
    }
  };

 

코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line.split(" ").map(Number));
}).on("close", () => {
  const [n, m, v] = input.shift();
  const graph = Array.from({ length: n + 1 }, () => []);
  input.forEach((el) => {
    const [s, e] = el;
    graph[s].push(e);
    graph[e].push(s);
  });
  graph.forEach((el) => el.sort((a, b) => a - b));

  const dfsCheck = Array(n + 1).fill(false);
  const dfsAns = [];
  const dfs = (curNode) => {
    if (dfsCheck[curNode]) return;
    dfsCheck[curNode] = true;
    dfsAns.push(curNode);
    for (let next of graph[curNode]) {
      if (!dfsCheck[next]) {
        dfs(next);
      }
    }
  };

  const bfsCheck = Array(n + 1).fill(false);
  const bfsAns = [];
  const bfs = () => {
    const queue = [v];

    while (queue.length > 0) {
      const curNode = queue.shift();
      if (bfsCheck[curNode]) continue;
      bfsCheck[curNode] = true;
      bfsAns.push(curNode);

      for (let next of graph[curNode]) {
        if (!bfsCheck[next]) {
          queue.push(next);
        }
      }
    }
  };
  dfs(v);
  bfs(v);
  console.log(dfsAns.join(" "));
  console.log(bfsAns.join(" "));

  process.exit(0);
});