(javascript) 프로그래머스 가장 먼 노드

[문제링크]

https://programmers.co.kr/learn/courses/30/lessons/49189?language=javascript

[문제]

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

[풀이]

bfs문제는 queue 자료구조를 이용하여 가까운 노드부터 우선적으로 처리합니다. 이번 문제는 응용이 필요하지않은 기초적인 문제라 생각됩니다.

• 첫번째 문제 풀이
  bfs 문제풀이를 할때, queue를 먼저 떠올리고, 그 queue에는 지금 탐색해야할 같은 depth를 가진 node들이 담겨있어야 합니다.

1. 변수는 visited_arr, level_arr, queue 를 선언하였습니다.
2. queue를 선입선출하여 그 노드와 인접한 노드들을 edge들을 검색한뒤 queue에 넣고 이 문제에 필요한 최대 depth (level_arr)를 갱신합니다.
3. visit하지 않은 node가 없을때까지 진행합니다.

(주의) edge에 있는 간선들은 양방향이지만 정렬이 되어있지 않기때문에 $[a,b]$에서 $a,b$둘다 검색하여야 합니다.

[성공코드]

function solution(n, edge) {
    var answer = 0;
    return bfs(edge,1,n);
}

function bfs(arr,start,end){
    var visited=new Array(end+1)
    var level=new Array(end+1)
    var queue=[start]
    level[0]=0
    level[start]=0
    visited[start]=true
    var lev
    while( queue.length){
        
        var node = queue.shift()
        lev = level[node]+1
        for( var edge of arr){
            if(edge[0]==node && visited[edge[1]]==undefined) {
                queue.push(edge[1])
                visited[edge[1]]=true
                level[edge[1]]=lev
            }
            else if(edge[1]==node && visited[edge[0]]==undefined) {
                queue.push(edge[0])
                visited[edge[0]]=true
                level[edge[0]]=lev
            }
        }
    }
    return level.filter((i)=>i==lev-1).length
}