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

문제 정보

• 프로그래머스 문제 링크
• 난이도 : level 3

 

해결 방법

최단 경로로 이동했을 때 가장 멀리 떨어진 노드를 구해야 해서 BFS 알고리즘을 사용했습니다.

BFS 는 다음에 탐색할 정보를 queue 에 넣기 때문에 depth 의 경우 shortestList 에 따로 저장하고 현재 노드인 curNodeNum 의 depth 에 1 을 더한 값을 nextNode 의 shortestList 에 추가했습니다. BFS 의 특성상 depth 는 증가만 하기 때문에 이미 최단경로의 depth 를 구한 경우에는 저장하지 않도록 했습니다.

최단경로를 모두 탐색하고 최종적으로 shortestList 에 있는 최대값의 개수를 counting 했습니다. 

 

소스 코드

 

function solution(n, edge) {
    let answer = 0;
    const visited = []; // 방문 여부 판단
    const queue = []; // 방문할 노드
    const shortestList = []; // shortestList[node] = node 의 depth

    const bfs = function(startNodeNum, depth){
        queue.push(startNodeNum);
        shortestList[startNodeNum] = depth;

        while(0 < queue.length){
            const curNodeNum = queue.shift();
            
            // 현재 노드가 visited 에 없을 경우
            if(visited.indexOf(curNodeNum) < 0){
                visited.push(curNodeNum);
                depth = shortestList[curNodeNum] + 1;

                const nextNodes = edge.filter(el => (el[0] == curNodeNum || el[1] == curNodeNum))
                                      .map(el => el[0] == curNodeNum ? el[1] : el[0]);

                //console.log(`curNodeNum:${curNodeNum} / visited:${visited}`);
                //console.log(`nextNodes:${nextNodes}`);
                for(let idx = 0; idx < nextNodes.length; idx++){
                    queue.push(nextNodes[idx]);
                    // 최단거리가 갱신되는 일을 막기 위해 조건 추가
                    if(shortestList[nextNodes[idx]] == undefined){
                        shortestList[nextNodes[idx]] = depth;
                    }
                }
            }

        }
    };

    bfs(1, 0);

    // 가장 긴 최단거리 개수
    shortestList.shift(); // Math.max 계산을 위해 0번째 인덱스 삭제
    answer = shortestList.filter(el => el == Math.max(...shortestList)).length
    return answer;
}

 

추가 내용

최단 경로를 찾는 경우 Dijkstra, Bellman-ford, Floyd-warshall 등 조금씩 다른 알고리즘을 통해서도 구할 수 있는데 추후에 다양한 방법으로 풀어볼 예정입니다.

 

참고 자료

• 알고리즘 - 다익스트라 알고리즘(Dijkstra's algorithm) : 모든 정점까지의 최단 경로 구하기
• 벨만-포드 알고리즘
• 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘