[백준 문제풀이] 1260번 DFS와 BFS

1260 DFS와 BFS

문제

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

입력

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

출력

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

문제 풀이

// 백준 1260번 DFS 와 BFS

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

const nmv = input.shift().split(" ").map(Number);

let graph = Array.from(Array(nmv[0] + 1), () => new Array());

for (let i = 1; i <= nmv[1]; i++) {
  let node = input.shift().split(" ").map(Number);
  graph[node[0]].push(node[1]);
  graph[node[1]].push(node[0]);
}
graph.map((el) => el.sort((a, b) => a - b));

let dfsAns = [];
let bfsAns = [];

const dfs = (graph, v, visited, ans) => {
  // 현재 노드 방문 처리
  visited[v] = true;
  ans.push(v);
  // 현재 노드와 인접한 다른 노드들을 재귀적으로 방문
  for (i of graph[v]) {
    // 방문한 적 없는 노드
    if (!visited[i]) {
      dfs(graph, i, visited, ans);
    }
  }
  return ans;
};

const bfs = (graph, start, visited, ans) => {
  let queue = [];
  queue.push(start);
  // 현재 노드 방문 처리
  visited[start] = true;
  // 큐가 빌 때까지 반복
  while (queue.length != 0) {
    // 큐에서 원소 뽑아서 출력 (선입선출)
    let v = queue.shift();
    ans.push(v);
    // 아직 방문하지 않은 인접 원소들 큐에 삽입
    for (i of graph[v]) {
      if (!visited[i]) {
        queue.push(i);
        visited[i] = true;
      }
    }
  }
  return ans;
};

let visited = Array(9).fill(false);
let a = dfs(graph, nmv[2], visited, dfsAns);
visited.fill(false);
let b = bfs(graph, nmv[2], visited, bfsAns);

console.log(...a);
console.log(...b);

입력을 받아서 인접 리스트를 만들어서 정렬을 해야했다. 작은 번호부터 해야하니까 정렬 해주는 부분이 꼭 필요하다.

또한 원래 구현했던 DFS, BFS에서는 그때 그때 콘솔 출력을 하여 줄바꿈이 되어서 출력되었기 때문에 출력 방식을 맞춰주기 위해선 미리 담아두었다가 출력해야했다.

앞서 문제 풀 때 배열 원소 출력시 줄바꿈 없이 출력하려고 별 난리를 쳤었는데 그냥 spread 연산자 썼으면 되는 걸... js 처음 배웠을 땐 당연하게 spread 썼는데 초심을 잃어 까먹었었나😅