[프로그래머스] 가장 먼 노드(JavaScirpt)

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

난이도 : level 3

 

풀이 과정 :

Bfs를 이용해서 푸는 문제였다.

bfs만 알면 매우 간단한 문제라 js에서는 큐를 직접 구현하는 것이 핵심이다

풀다가 실수한 부분은 2차원 배열을 초기화 하는 부분에서 배열의 크기를 n+1로 안해서 계속 에러가 났엇다;;

그리고 풀고나서 다른 사람 코드를 보니 filter 함수를 이용해 이쁘게 답을 출력하던데 참고할만한 부분이었다.

 

ps. 근데 그래프문제는 그냥 C++이 편한거 같다...연습겸 js로 풀어보고 있긴한디.. 불편하네요

 

 

전체 코드 :

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  push(value) {
    this.queue[this.rear++] = value;
  }
  pop(){
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front++;
    return value;
  }
    
  top() {
    return this.queue[this.front];
  }    
  size() {
      return this.rear-this.front;
  }
}

function solution(n, edge) {
    var answer = 0;
    
    let graph = Array.from(Array(n+1), () => []);
    
    for([a,b] of edge){
        graph[a].push(b);
        graph[b].push(a);
    }
    
    
    let dist = new Array(n+1).fill(0);
    let max = -1;
    let q = new Queue();

    q.push(1);
    dist[1] = 1;
    while(q.size()>0){
        let now = q.top();
        q.pop();
        for(let i=0;i<graph[now].length;i++){
            let next = graph[now][i];
            if(!dist[next]){
                q.push(next);
                dist[next] = dist[now] + 1;
                if(max<dist[next]) max = dist[next];
            }            
        }
    }
    
   for(let i=1;i<=n;i++){
       if(max === dist[i]) answer++;
   }
    return answer;
    
   // filter을 이용해 답 출력  
   // return dist.filter(item => item === max).length;
}