[Node.js] 백준 1260 :: DFS와 BFS

7번의 시도 끝에 성공...😵

DFS와 BFS

DFS / BFS가 뭔데,,

BFS와 DFS 모두 모든 정점을 방문한다는 것은 동일하지만, 각각 방문하는 경로가 다르다.

DFS

• DFS는 현재 정점과 연결된 정점 중 한 정점에만 방문할 수 있다.
• 단, 방문할 수 있는 정점들의 모든 경우의 수를 방문해봐야 한다.
  (1과 연결된 정점이 2, 3이라면 2를 방문하는 경우와 3을 방문하는 경우를 모두 수행해야 한다.)
• 방문했던 지점을 다시 거치는 것도 가능하다! (방문으로 따지지는 않으므로 결과를 담는 배열에 추가하지는 않는다.)

BFS

• BFS는 현재 정점과 연결된 정점을 동시에 모두 방문할 수 있다.
• 방문한 정점을 queue에 담아놓고, queue에 담긴 정점들을 앞에서부터 하나씩 꺼내서 해당 정점과 연결된 모든 정점을 (동시에) 방문한다.
• queue에 담긴 정점을 모두 방문하면 끝!
• 방문 여부를 담을 check 배열을 활용하면 중복을 피할 수 있다.

 

런타임 에러 (TypeError)

해당 정점과 연결된 정점이 하나도 없는 경우에 대한 처리를 해주지 않으면, 참조 에러가 발생한다!

연결된 정점이 있는 경우만 배열 순회를 수행하도록 if문을 추가해서 해결했다✌🏻

위 사례를 확인할 수 있는 반례

input
5 4 1
2 3
3 4
4 5
5 2

output
1
1

 

풀이

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

// 시작할 정점
const start = Number(input[0].split(" ")[2]);

// 각 정점과 연결된 정점을 담은 배열
const temp = [];
for (let i = 1; i < input.length; i++) {
  const left = Number(input[i].split(" ")[0]);
  const right = Number(input[i].split(" ")[1]);
  if (temp[left]) temp[left] = [...temp[left], right];
  else temp[left] = [right];
  if (temp[right]) temp[right] = [...temp[right], left];
  else temp[right] = [left];
}
// 오름차순으로 정렬
const nodeList = temp.map((el) => el.sort((a, b) => a - b));

// DFS
const dfsResult = [];
const dfs = (vertex) => {
  if (dfsResult.includes(vertex)) return;
  dfsResult.push(vertex);
  // 정점과 연결된 정점이 있는 경우만 수행
  if (nodeList[vertex])
    nodeList[vertex].forEach((el) => {
      dfs(el);
    });
};
dfs(start);

// BFS
const bfsResult = [];
const check = [];
const queue = [start];
const bfs = () => {
  const vertex = queue.shift();
  if (check[vertex]) return;
  if (bfsResult.includes(vertex)) return;
  check[vertex] = true;
  bfsResult.push(vertex);
  if (nodeList[vertex])
    nodeList[vertex].forEach((el) => {
      queue.push(el);
    });
};
while (queue.length) {
  bfs(start);
}

console.log(...dfsResult);
console.log(...bfsResult);