[백준1260_자바스크립트(javascript)] - DFS와 BFS

🔴 문제

DFS와 BFS

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const [n, m, v] = inputs.shift();
const info = Array.from({ length: n + 1 }, () => []);

for (const input of inputs.sort((a, b) => a[0] - b[0] || a[1] - b[1])) {
  const [a, b] = input;
  info[a].push(b);
  info[b].push(a);
}

for (let i = 1; i <= n; i++) {
  info[i].sort((a, b) => a - b);
}

let ans = '';
const visitedDFS = Array.from({ length: n + 1 }, () => false);

const dfs = (node) => {
  if (visitedDFS[node]) return;
  ans += node + ' ';

  for (let i = 0; i < info[node].length; i++) {
    visitedDFS[node] = true;
    dfs(info[node][i]);
  }
};

const visitedBFS = Array.from({ length: n + 1 }, () => false);
const bfs = (node) => {
  const q = [node];

  while (q.length) {
    const target = q.shift();
    if (visitedBFS[target]) continue;
    ans += target + ' ';

    visitedBFS[target] = true;

    q.push(...info[target]);
  }
};

visitedDFS[0] = true;
dfs(v);
console.log(ans.trim());

ans = '';

visitedBFS[0] = true;
bfs(v);
console.log(ans.trim());

🟢 풀이

⏰ 소요한 시간 : -

DFS를 수행한 결과와 BFS를 수행한 결과를 출력하는 문제
info라는 배열을 만들고 정점과 간선 정보를 인접 리스트 형태로 저장한다. 이 때 양방향 연결이므로 a-b 연결과 b-a 연결 모두 info에 넣어준다.
이 때, 정점이 여러개인 경우 정점 번호가 작은 것을 만족한다 라는 조건을 충족하도록 각 배열의 내부를 정렬해준다.
방문체크를 위한 dfs, bfs 방문배열을 만들고 정답을 출력할 문자열도 만들어 준다.
그 후 dfs 내부를 구현해준다. 현재 탐색중인 노드가 방문한 노드라면 재귀호출 종료
방문한 노드가 아니라면 현재 방문했다는 의미로 ans 문자열에 추가 후 현재 노드랑 연결된 노드를 재귀호출한다. 여기서도 방문처리 필수!
bfs도 현재 노드를 큐에 넣고 방문하지 않은 노드를 차례대로 탐색하면 된다.

🔵 Ref