[JS] 프로그래머스 가장 먼 노드 풀이

리팩토링 전 풀이완료 코드

function solution(n, edges) {
   let graph = {}
   let queue = [[1,0]]
   let table = {1:0}
   edges.forEach(([start,end])=>{
       start in graph ? graph[start].push(end) : graph[start]=[end]
       end in graph ? graph[end].push(start) : graph[end]=[start]
   })
    
    while(queue.length){
        const [v,dist]= queue.shift()
        for(let i=0; i<graph[v].length; i++){
            if(!(graph[v][i] in table) || table[graph[v][i]] > dist+1){
                table[graph[v][i]] = dist+1
                queue.push([graph[v][i],dist+1])
            }
        }
    }
    const maxDistance = Math.max(...Object.values(table))
    return Object.values(table).filter(dist=>dist===maxDistance).length
}

리팩토링하기

1. index를 사용해서 저장할 수 있는 자료인 경우 배열로 저장

// before
let table = {}

// after
let distance = Array(n + 1).fill(0);
distance[1] = 1

• 거리를 저장하는 배열 생성
• distance[3]은 3번 노드까지의 거리

2. for문 제거 => for ... of문

// before
for (let i = 0; i < graph[v].length; i++) {
      if (!(graph[v][i] in table) || table[graph[v][i]] > dist + 1) {
        table[graph[v][i]] = dist + 1;
        queue.push([graph[v][i], dist + 1]);
      }
    }

// after
for (const dest of graph[v]) {
      if (distance[dest] === 0 || distance[dest] > dist + 1) {
        distance[dest] = distance[v] + 1;
        queue.push([dest, distance[v] + 1]);
      }
    }

회고

1. for문을 지양하고 고차함수, for..of등 의도가 명확히 드러나는 코드를 사용하자
2. 어떤 자료구조에 어떻게 데이터를 저장할 지 고민해보자
   • 무지성으로 {}에 모든 데이터를 담으려고 하지마라