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

[문제]

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

프로그래머스

 

[풀이]

노드 1부터의 최소 거리를 모두 구해야 하기 때문에 BFS를 활용하였습니다.

 

초기 세팅

• 양방향 그래프 정보를 저장하기 위해 이차원 배열 graph에 정보를 저장하였습니다.
• 방문한 정점을 저장하는 visit배열을 선언하고 false로 초기화 해주었습니다.
• 노드 1부터의 거리를 저장하는 dist 배열을 선언하고 0으로 초기화 해주었습니다.
• 노드를 방문하며 최대 거리 max를 저장하기 위해 max를 선언합니다.

 

큐를 활용해 그래프를 탐색하였는데, queue에서 정점 1개를 shift하여 해당 정점과 연결된 아직 방문하지 않은 정점들을 탐색하며 현재 정점의 dist정보 + 1을 저장하였습니다. 그래프를 탐색하는 과정에서 최대 거리 max를 갱신해주었습니다.

 

1을 뽑아서 2, 3 방문 후, dist[2] = 1, dist[3] = 1

2를 뽑아서 4, 5 방문 후, dist[4] = 2, dist[5] = 2

3을 뽑아서 6 방문 후, dist[6] = 2

 

따라서 모든 정점을 방문하고 난 후 dist배열은 다음과 같습니다.

[ 0, 0, 1, 1, 2, 2, 2 ]

 

최대 거리는 2 이므로 filter연산을 통해 dist에서 2의 개수를 구하면 answer은 3이 됩니다.

 

[코드]

function solution(n, edge) {
    var answer = 0;
    const graph = Array.from({length: n+1}, () => []);
    edge.forEach((item) => {
        graph[item[0]].push(item[1]);
        graph[item[1]].push(item[0]);
    });
    
    const findDist = () => {
        const dist = Array.from({length: n+1}, () => 0);
        const visit = Array.from({length: n+1}, () => false);
        let max = 0;
        const queue = [];
        visit[1] = true;
        queue.push(1);

        while(queue.length !== 0) {
            const q = queue.shift();
            for(let i=0;i<graph[q].length;i++) {
                const node = graph[q][i];
                if(visit[node]) {
                    continue;
                }
                dist[node] = dist[q] + 1;
                visit[node] = true;
                if(max < dist[node]) {
                    max = dist[node];
                }
                queue.push(node);
            }
        }
        answer = dist.filter((d) => d === max).length;
    }
    
    findDist();

    return answer;
}