BOJ-백준 1260번 DFS와 BFS Javascript Node.js 문제 풀이와 반례

BOJ-백준 1260번 DFS와 BFS Javascript Node.js 문제 풀이와 반례 입니다.

링크 : https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

 

 

✅ Node.js 정답 코드 입니다. 더보기 클릭!

const fs = require("fs");

const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((num) => num.split(" "));
const [N, M, start] = input.shift().map((x) => parseInt(x));
const graph = input.map((x) => [Number(x[0]), Number(x[1])]);


/**
 * DFS
 */

const dfs_route = Array(N + 1).fill(0);
dfs(start);
function dfs(i) {
  if (dfs_route[i] > 0) return;
  dfs_route[i] += 1;
  process.stdout.write(i + " ");
  const available = [];
  for (g of graph) {
    if (g[0] == i) available.push(parseInt(g[1]));
    if (g[1] == i) available.push(parseInt(g[0]));
  }
  const sort = available.sort((a, b) => a - b);
  sort.map((a) => dfs(a));
}
console.log("");
/**
 * BFS
 */
const bfs_route = Array(N + 1).fill(0);
const que = [];
que.push(Number(start));
while (que.length > 0) {
  const node = que.shift();
  bfs(node);
}

function bfs(i) {
  if (bfs_route[i] > 0) return;
  bfs_route[i] += 1;
  process.stdout.write(i + " ");
  const available = [];
  for (g of graph) {
    if (g[0] == i) available.push(parseInt(g[1]) * 1); // 연결된 노드를 찾고 가능 배열에 push
    if (g[1] == i) available.push(parseInt(g[0]) * 1); // 연결된 노드를 찾고 가능 배열에 push
  }
  const sort = available.sort((a, b) => a - b);
  que.push(...sort);
}

 

📌 해설

간단하게 DFS 와 BFS 를 구현하는 문제입니다.

javascript 로 풀때 sort() 사용 시,

[2, 1, 3, 10, 11] => [1, 10, 11,  2, 3, ] 로 정렬 되는데, 따로 조건을 걸지 않으면 배열에 있는 원소 타입을 모두 String 문자열 기준으로 정렬되기 때문에 오답을 얻을 수 있습니다. 

따라서 available.sort((a, b) => a - b); 로 문자열이 아닌 정수를 정렬 할 수 있도록 해줍니다. 

 

 

1.

const fs = require("fs");

const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((num) => num.split(" "));
const [N, M, start] = input.shift().map((x) => parseInt(x));
const graph = input.map((x) => [Number(x[0]), Number(x[1])]);

 

입력을 받아줍니다. 

 

2.

/**
 * DFS
 */

const dfs_route = Array(N + 1).fill(0);
dfs(start);
function dfs(i) {
  if (dfs_route[i] > 0) return;
  dfs_route[i] += 1;
  process.stdout.write(i + " ");
  const available = [];
  for (g of graph) {
    if (g[0] == i) available.push(parseInt(g[1]));
    if (g[1] == i) available.push(parseInt(g[0]));
  }
  const sort = available.sort((a, b) => a - b);
  sort.map((a) => dfs(a));
}
console.log("");

 

DFS 를 구현합니다. 

dfs_route 에서 방문 체크를 할 수 있도록 합니다. 

재귀로 dfs 를 호출하여 구현하였습니다. 

 

 

3.

/**
 * BFS
 */
const bfs_route = Array(N + 1).fill(0);
const que = [];
que.push(Number(start));
while (que.length > 0) {
  const node = que.shift();
  bfs(node);
}

function bfs(i) {
  if (bfs_route[i] > 0) return;
  bfs_route[i] += 1;
  process.stdout.write(i + " ");
  const available = [];
  for (g of graph) {
    if (g[0] == i) available.push(parseInt(g[1]) * 1); // 연결된 노드를 찾고 가능 배열에 push
    if (g[1] == i) available.push(parseInt(g[0]) * 1); // 연결된 노드를 찾고 가능 배열에 push
  }
  const sort = available.sort((a, b) => a - b);
  que.push(...sort);
}

 

BFS를 구현해주었습니다. 

큐로 구현했고, 방문체크는 dfs와 동일한 방식으로 진행하였습니다. 

 

 

 

📌 반례

문제 예제에 없는 반례입니다. 

예제가 다 맞아도 '틀렸습니다'이면 확인 해보면 좋습니다. 

11 10 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11

 

출력

1 2 3 4 5 6 7 8 9 10 11

1 2 3 4 5 6 7 8 9 10 11

 

 

 

::

sort 가 따로 조건이 없으면 문자열 정렬인줄 모르고 이것저것 노력해본 흔적도 그대로 남겨두었습니다.

수치스러우면 기억에 더 오래 남거든요 ㅎ