[프로그래머스] level3. 가장 먼 노드 (javascript)

문제

코딩테스트 연습 - 가장 먼 노드

나의 풀이

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

처음에 node의 방향성을 생각하다 못풀었다.

너무 어렵게 생각하지 말고, node 단위로 생각하면 쉽게 접근이 가능할 것 같다.

 

function solution(n, edge) {
    let visited = new Array(n+1).fill(0)
    let level = new Array(n+1).fill(0)

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

    while(queue.length){
        let target = queue.shift();
        let lev = level[target] +1
        edge.forEach((el)=>{
            if(el[0] === target && visited[el[1]] !== 1){
                visited[el[1]] = 1
                queue.push(el[1])
                level[el[1]] = lev
                return
            }
            if(el[1] === target && visited[el[0]] !== 1){
                visited[el[0]] = 1
                queue.push(el[0])
                level[el[0]] = lev
            }
        })
    }

    let MAX = Math.max(...level)
    return level.filter(el=>el===MAX).length
}

풀이

bfs 방식을 기반으로 풀이를 하였다.
Array를n+1개를 선언한 것은 queue에 넣다 뺴는 과정에서 인덱스 값을 편하게 쓰기 위한 것이다.

visited 가 방문여부, level이 몇번 이동해서 이 node에 도착했는가, 즉 거리이다.
이 문제는 edge의 [5,2] 배열이 [2,5]와 같은 의미가 되므로 순서만 바꿔서 if문을 2번 적용헤야된다.

또한, 자료를 찾다보니, 다익스트라 알고리즘 얘기를 봐서 이 개념도 함께 보면 좋을 것 같다.

23. 다익스트라(Dijkstra) 알고리즘