[JS] 가장 먼 노드

BFS + DP 를 조합하여 해결할 수 있는 문제였다. (3단계 치곤 쉬운것 같기도?)

 

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

 

 

단순하게 가장 먼 노드들을 저장하면 되기 때문에 1번 노드부터 큐를 활용한 BFS를 구현하여 해결하였다.

 

이때 노드의 개수와 간선의 개수가 각각 20000,50000개이므로 DP를 활용해서 방문 했는지 안했는지 체크해주면 되는데 나는 문제를 해결하기 위해서 방문한 김에 거리를 기록해줘서 후에 정답을 도출할 수 있게 하였다.

 

 

 

 

 

function solution(n, edge) {
    //그래프 생성
    const graph = [...Array(n+1)].map(_ => [])
    for (const [s,e] of edge){
        graph[s].push(e)
        graph[e].push(s)
    }
    
    //정답을 저장 및 방문여부 조사용 배열
    const visited = Array(n+1).fill(0)
    
    //JS엔 큐가 없어서 시간복잡도 아끼기 위해 아래처럼 구현
    const que = [[1,0]]
    let queIdx = 0
    while(queIdx < que.length){
        const [node,dist] = que[queIdx]
        //방문했다면 그냥 넘김
        if(visited[node]){
            queIdx++
            continue
        }
        //방문처리
        visited[node] = dist
        
        //다음 노드를 하나씩 순회
        for(const nxNode of graph[node]){
            que.push([nxNode,dist+1])
        }
        queIdx++
    }
    
    //최대값의 개수를 찾음
    let ret = 0
    let maxValue = 0
    for (let i = 2 ; i <= n ; i++){
        if(visited[i] > maxValue) {
            ret = 1
            maxValue = visited[i] 
        } else if (visited[i]===maxValue) ret ++
    }
    
    return ret
}

 

 

끄읏 -!