[JS][백준]1260_DFS와 BFS

문제 번호

1260번: DFS와 BFS

 

 

알고리즘 분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

문제 풀이

 기본적인 DFS와 BFS를 구현하면 되는문제이다.

DFS구현에는 STACK을 사용하는것이 편리한데 C++과는 다르게 JS에는 stack이라는 자료구조를 사용할 수 있는 라이브러리가 따로 존재하지 않는다. 또한 BFS는 Queue를 사용하여 구현하는것이 편리한데 Queue를 사용할 수 있는 라이브러리또한 존재하지 않는다. 

 하지만 상관없다. 기존의 배열을 STACK과 Queue처럼 사용할 수 있기 때문이다.

 

우선 문제에서 주어진 내용을 입력받는다.

const fs = require('fs');
const input = fs.readFileSync('DFS와 BFS/input.txt').toString().trim().split('\n');

const NMV = input.shift().split(' ');
const N = Number(NMV.shift());
const M = Number(NMV.shift());
const V = Number(NMV.shift());

graph = new Array(N + 1).fill(0, 0, N + 1);
for (let i = 0; i <= N + 1; i++) {
  graph[i] = new Array(N + 1).fill(0, 0, N + 1);
}

for (let i = 0; i < M; i++) {
  const xy = input.shift().split(' ');
  const x = Number(xy.shift());
  const y = Number(xy.shift());

  graph[x][y] = 1;
  graph[y][x] = 1;
}

 shitft 함수는 O(n)의 시간복잡도를 갖기때문에 문제에 따라서 shift 함수를 여러번 사용하면 시간초과에 걸리는 경우도 있다. map 함수와 split 함수를 적절히 조합하여 한번에 입력받는 방법을 더 연습해야겠다.

 

DFS

let DFS = function (node) {
  let answer = '';
  let visited = new Array(N + 1).fill(false, 0, N + 1);
  let stack = [];

  stack.push(node);

  while (stack.length > 0) {
    let cur = stack.pop();

    if (!visited[cur]) {
      visited[cur] = true;
      answer += cur + ' ';

      for (let next = N; next >= 1; next--) {
        if (!visited[next] && graph[cur][next])
          stack.push(next);
      }

    }
  }
  console.log(answer);
}

DFS를 구현했다. console.log를 매번 사용하면 시간초과가 날 수 도 있다는 생각이 들어서 answer 문자열에 모두 넣어준 뒤 출력하였다. 

 

BFS

let BFS = function (node) {
  let answer = '';
  let visited = new Array(N + 1).fill(false, 0, N + 1);
  visited[node] = true;  

  let Queue = [];
  Queue.push(node);

  while (Queue.length > 0) {
    let cur = Number(Queue.shift());
    answer += cur + ' ';
    for (let next = 1; next <= N; next++) {
      if (!visited[next] && graph[cur][next]) {
        visited[next] = true;
        Queue.push(next);
      }
    }
  }
  console.log(answer);
}

BFS를 구현하였다. 특별한 내용은 없다.

 

전체코드

const fs = require('fs');
const input = fs.readFileSync('DFS와 BFS/input.txt').toString().trim().split('\n');

const NMV = input.shift().split(' ');
const N = Number(NMV.shift());
const M = Number(NMV.shift());
const V = Number(NMV.shift());

graph = new Array(N + 1).fill(0, 0, N + 1);
for (let i = 0; i <= N + 1; i++) {
  graph[i] = new Array(N + 1).fill(0, 0, N + 1);
}

for (let i = 0; i < M; i++) {
  const xy = input.shift().split(' ');
  const x = Number(xy.shift());
  const y = Number(xy.shift());

  graph[x][y] = 1;
  graph[y][x] = 1;
}

let BFS = function (node) {
  let answer = '';
  let visited = new Array(N + 1).fill(false, 0, N + 1);
  visited[node] = true;  

  let Queue = [];
  Queue.push(node);

  while (Queue.length > 0) {
    let cur = Number(Queue.shift());
    answer += cur + ' ';
    for (let next = 1; next <= N; next++) {
      if (!visited[next] && graph[cur][next]) {
        visited[next] = true;
        Queue.push(next);
      }
    }
  }
  console.log(answer);
}

let DFS = function (node) {
  let answer = '';
  let visited = new Array(N + 1).fill(false, 0, N + 1);
  let stack = [];

  stack.push(node);

  while (stack.length > 0) {
    let cur = stack.pop();

    if (!visited[cur]) {
      visited[cur] = true;
      answer += cur + ' ';

      for (let next = N; next >= 1; next--) {
        if (!visited[next] && graph[cur][next])
          stack.push(next);
      }

    }
  }
  console.log(answer);
}

DFS(V);
BFS(V);

특이사항

 처음 BFS와 DFS를 배울때 이론적으로는 이해하였으나 코드로 구현하는것이 너무너무너무 어려웠다.

그래서 여러코드들을 찾아보고 가장 기본적이면서 외우기 쉬운 코드를 그냥 암기하여 사용했다. 어려운 알고리즘 문제들이 등장할때 일단 외우고 여러번 사용하면서 이해해나가는 방법도 괜찮은것 같다.