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

사용 언어 : javascript
해결 날짜 : 2022-10-21
해결 방법 :
- 1번 노드로부터의 각 거리 distance 0으로 초기화
- 각 노드와의 연결을 표현할 graph 초기화
- edge를 돌며 양방향 연결 (graph에 push)
- queue에 1번 노드부터 추가 후 반복문
- 현재 노드와 연결된 다음 노드를 돌며 distance가 0이고 (아직 방문하지 않음), 다음 노드가 0이 아니면
- queue에 push(), distance 업데이트
- 이 때 최대값도 갱신
회고 :
- BFS 말고도 Queue 자료구조 구현해서 풀어보기

코드

function solution(n, edge) {
    const graph = Array.from({length: n}, () => []);
    const distance = Array.from({length: n}, () => 0);
        
    for (const e of edge) {
        const [from, to] = [e[0] - 1, e[1] - 1];
        graph[from].push(to);
        graph[to].push(from);
    }
        
    const queue = [0];
    let max = 0;
    while (queue.length) {
        const current = queue.shift();
        for (const next of graph[current]) {
            if (!distance[next] && next !== 0) {
                queue.push(next);
                distance[next] = distance[current] + 1;
                if (distance[next] > max) max = distance[next];
            }
        }
    }
        
    return distance.filter((e) => e === max).length;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges