[백준 알고리즘] Node.js 24444. 알고리즘 수업 - 너비 우선 탐색 1

1. 문제

https://www.acmicpc.net/problem/24444

24444번: 알고리즘 수업 - 너비 우선 탐색 1

 

2. 풀이

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [n,m,r] = inputs.shift().split(' ').map(v => +v);

const numMap = new Map();
inputs.forEach(v => {
  let [a,b] = v.split(' ').map(vv => +vv);

  if(numMap.has(a)) numMap.get(a).push(b); 
  else numMap.set(a, [b])
  
  if(numMap.has(b)) numMap.get(b).push(a);
  else numMap.set(b, [a])
})

const visited = new Array(n + 1).fill(0);
const queue = [];
let count = 1;

queue.push(r);
visited[r] = 1;

while(queue.length){
  const t = queue.shift();
  const nodes = numMap.get(t).sort((a,b) => a-b);

  for(let node of nodes){
    if(visited[node] === 0){
      visited[node] = ++count;
      queue.push(node)
    }
  }
}

console.log(visited.slice(1).join('\n'))

- map 형태로 그래프를 만들었다. 이후 queue를 이용하여 방문한 곳에 count를 해주었다.

 

3. 정리

- 아직 bfs에 대한 부분의 이해도가 부족하다.