프로그래머스 - [Level 3] 가장 먼 노드(JAVASCRIPT)

프로그래머스 가장 먼 노드

카테고리 : 그래프/BFS

풀이 과정은 다음과 같다.

1) 인접 리스트를 만든다.
이때, 인접한 노드들은 서로 양방향이므로

[from,to] , [to,from]

두 케이스 전부 인접 리스트의 간선으로 만들어준다.

2) Bfs 방식으로 인접리스트를 탐색하면서 각 노드의 거리를 visit 배열에 기록해준다.
 1. queue에 [노드, 거리]를 원소로 넣어준다. 
 2. 노드 n 에서 이동할 수 있는 인접 노드를 탐색한다.(시작은 1번 노드 부터)
 - 방문하지 않았다면 queue 배열에 [인접 노드, 거리+1]을 원소로 넣어준다.
 - 이미 방문했다면(visit 배열로 최단 거리가 이미 기록되었다면) 무시해준다.
 
3) 2)번의 과정을 거치고나면, 각 노드와 1번 노드와의 거리를 원소로하는
visit 배열이 만들어져있다.

visit 배열에서 최대 값을 추출하고, 이 최대값과 일치하는 원소의 개수를 return 한다.

소스 코드

function solution(n, edge) {
    let answer = 0;
    const list = Array.from(Array(n),()=>Array());    
    const makelist=()=>{
        edge.forEach((idx)=>{
           list[idx[0]-1].push(idx[1]-1);
           list[idx[1]-1].push(idx[0]-1);
        })
    };
    
    const bfs=()=>{
        let visit=Array.from(Array(n).fill(0));
        let queue=[[0,1]];
        visit[0]=1;
        while(queue.length){
            let now=queue.shift();
            let node=now[0],count=now[1];
            list[node].forEach(next=>{
                if(visit[next]===0){
                    queue.push([next,count+1]);
                    visit[next]=count+1;
                }
            });
        }
        const maxi=Math.max.apply(null,visit);
        answer=visit.filter((a,idx)=>a===maxi).length;
    }
    
    makelist();
    bfs();
    return answer;
}