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

1. 문제

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

24445번: 알고리즘 수업 - 너비 우선 탐색 2

 

2. 풀이

- 처음 풀이는 24444번과 거의 비슷하게 풀었다. 24444번은 오름차순 정렬이었고, 24445번은 내림차순 정렬이기 때문에 sort() 부분만 수정하여 제출하였다.

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) => b-a);

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

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

- 19% 정도에서 TypeError 발생... 24444번은 성공했는데 어떤 테스트케이스 때문에 그런건지 이해를 할 수 없다.

 

- 그래서 map 대신 array로 변경

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

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

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

  graph[a].push(b);
  graph[b].push(a);
})


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

while(queue.length){
  const t = queue.shift();
  const nodes = graph[t].sort((a,b) => b-a);

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

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

- 아무래도 map() 부분에서 에러가 발생한 듯 하다. 이번건 통과!