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

아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

최단거리 계산에 가장 유리한 BFS(너비 우선 탐색)을 하면 효율적으로 코드를 작성할 수 있다!
1. 입력받은 그래프를 인접리스트 형식으로 변환
2. BFS 탐색을 통해 각 노드까지의 최단거리 기록
3. 최단 거리 배열에서 가장 큰 값의 개수를 세서 반환

여기서, distance 배열은 노드 번호를 인덱스로 이용해서 1번 노드부터의 거리를 저장하고,
visited 배열을 사용해 중복 방문을 방지한다.
JS에서는 visited를 빈배열로 시작해 값을 추가해서 includes를 통해 체크했는데 그것보다 False로 초기화한 후에 T/F값을 체크하는게 더 효율적인 것 같다 .. !

코드

---

1. Python

from collections import deque

def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    for s, e in edge:
        graph[s].append(e)
        graph[e].append(s)
    
    distance = [0] * (n + 1)
    visited = [False] * (n + 1)
    q = deque([1])
    visited[1] = True
    
    while q:
        cur = q.popleft()
        for next in graph[cur]:
            if not visited[next]:
                visited[next] = True
                distance[next] = distance[cur] + 1
                q.append(next)
    maxDistance = max(distance)
    return distance.count(maxDistance)

2. JS

function solution(n, edge) {
    let graph = Array.from({length: n+1}, () => []);
    for(const [s, e] of edge){
        graph[s].push(e);
        graph[e].push(s);
    }
    
    const distance = Array(n+1).fill(0);
    const q = [1];
    const visited = [1];
    let head = 0;
    
    while(head < q.length){
        const cur = q[head++];
        
        for(const next of graph[cur]){
            if(!visited.includes(next)){
                visited.push(next);
                distance[next] = distance[cur] + 1
                q.push(next);
            }
        }
    }
    
    const maxDistance = Math.max(...distance);
    return distance.filter(d => d === maxDistance).length;
}

결과

---