[백준 1260번] BFS/DFS(너비 우선 탐색/깊이 우선 탐색) - DFS와 BFS

✨ 문제 ✨

✨ 정답 ✨

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim();

// const fs = require('fs'); 
// let input = fs.readFileSync('/dev/stdin').toString().trim();

input=input.split('\n')

// N: 정점 개수,  M: 간선 개수,  V: 탐색을 시작할 정점의 번호
let [N, M, V]=input[0].split(' ').map(Number);

// 그래프 만들어주기
let graph=new Array(N+1); // 왜 N+1 하는거지? 정점 번호가 1부터 N까지라서 그런 건가

for (let i=0;i<graph.length;i++){
  graph[i]=[];
}

for (let i=0;i<M;i++){
  let [from, to]=input[i+1].split(" ").map(Number);
  // 양방향이니까 둘 다 push 해줌.
  graph[from].push(to);
  graph[to].push(from);
}
graph.forEach((el)=>{
  el.sort((a,b)=>a-b);
})


// 이제 DFS를 만들어 볼까요
let visited=new Array(N+1).fill(0);
let answer_dfs=[];
const DFS=(V)=>{
  if (visited[V]===1){
    return;
  }
  visited[V]=1;
  answer_dfs.push(V);
  for (let i=0;i<graph[V].length;i++){
    let next=graph[V][i];
    if (visited[next]===0){
      DFS(next);
    }
  }
}
DFS(V);
console.log(answer_dfs.join(' '))


// 이제 BFS를 만들어 볼까요
visited.fill(0);
let answer_bfs=[];
const BFS=(V)=>{
  // BFS는 너비 우선 탐색이니까 같은 레벨에 있는 정점을 하나씩 방문해야 함.
  // 그러므로 같은 레벨에 있는 정점을 배열로 만들어서 방문할 때마다 shift 해주어야 함.
  let queue=[V];
  while(queue.length){
    let current=queue.shift();
    if (visited[current]===1){
      continue;
    }
    visited[current]=1;
    answer_bfs.push(current);
    for (let i=0;i<graph[current].length;i++){
      let next=graph[current][i];
      if (visited[next]===0){
        queue.push(next);
      }
    }
  }
}
BFS(V);
console.log(answer_bfs.join(' '))

🧵 참고한 정답지 🧵

https://velog.io/@ywc8851/%EB%B0%B1%EC%A4%80-1260-DFS%EC%99%80-BFS-javascript

💡💡 기억해야 할 점 💡💡

예전에 그냥 내 머리로, 순전히 내 힘으로 풀겠다고 하다가 실패한 문제다. 백준에서 제공하는 예시 문제들에 대한 답은 제대로 나왔으나 반례 때문에 실패를 했었는데 이젠 그냥 고집을 버리기로 했다.
기본 원리를 알아야 다음 문제로 넘어가지...
DFS, BFS 구현 코드는 그냥 반드시 외워 두도록 하자.