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

문제링크

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

함수 설명

노드의 개수 n과
각 노드 간 연결을 나타낸 두 개의 숫자로 구성된 배열을 ex) [1, 3] 성분으로 갖는 배열 vertex
를 인자로 입력받습니다.

노드 1로부터 각 노드로 가는 최단거리를 구했을 때,
최단거리 중의 최곳값에 해당하는 노드가 몇 개인지 반환하는 문제입니다.

정답코드

const solution = (n,vertex) => {
    const nodeAndVertex = new Map();
    vertex.forEach(([from,to])=> {
        switch(nodeAndVertex.has(from)){
            case true:
                nodeAndVertex.set(from, nodeAndVertex.get(from).add(to));
                break;
            case false:
                nodeAndVertex.set(from, new Set([to]));
                break;
        }
        switch(nodeAndVertex.has(to)){
            case true:
                nodeAndVertex.set(to, nodeAndVertex.get(to).add(from));
                break;
            case false:
                nodeAndVertex.set(to, new Set([from]));
                break;
        }
    });
    const queue = [[1, 0]];
    const visited = new Map();
    visited.set(1,0);

    while(queue.length){
        const [cur, distance] = queue.shift();
        const linkedNodes = nodeAndVertex.get(cur) || [];
        linkedNodes.forEach((next)=> {
            if (!visited.has(next)){
                visited.set(next, distance + 1);
                queue.push([next, distance + 1]);
            }

        });
    }

    const max = Math.max(...visited.values());
    const answer = Array.from(visited.values()).filter(x=> x === max).length
    return answer;
}

해설

1. 그래프생성

nodeAndVertex에 key:value 쌍으로 "노드번호: 연결된 노드 Set"을 저장합니다.

이때 vertex는 양방향 간선입니다. [1, 2]가 주어진 경우 1에 대응되는 set에 2를 넣어주고

또 그 반대로 2에 대응되는 set에도 1을 넣어주어야 합니다.

- 첫 두번째 줄 vertex.forEach 부터 보시면 알 수있습니다.

 

 

2. dfs

큐에 현재 노드와 거리를 담은 배열을 삽입합니다.
방문노드를 체크하는 로직에서, 단순히 방문여부만 확인하는 게 아니라,

처음 1번 노드로부터 거리도 저장해주어야 합니다. 따라서 visited를 map객체로 사용했습니다.

 

다음과같이 방문 노드에대한 거리 함께 저장합니다.

Map(6) { 1 => 0, 3 => 1, 2 => 1, 6 => 2, 4 => 2, 5 => 2 }

 

이후 visited map의 values중에 최댓값을 구한후, 해당 값이

몇개나 있는지   filter.(x => x ===max). length를 통해 계산했습니다.