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

1. 문제 요약

N개의 노드로 이루어진 무방향 그래프가 주어진다. 1번 노드에서 최단 경로로 이동했을 때 간선 수가 가장 많은 노드의 개수를 반환한다.

• 노드 수 2 ~ 20,000
• 간선 수 1 ~ 50,000

2. 접근

1번에서 각 노드까지의 최단 거리를 구하고, 그 중 최댓값과 같은 거리를 가진 노드 수를 세면 된다.

가중치 없는 그래프에서 최단 거리 = BFS. 한 번 도달한 노드는 다시 방문하지 않으므로, 처음 도달한 시점의 거리가 최단 거리이다.

3. 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        for (int[] e : edge) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        dist[1] = 0;

        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(1);

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : graph.get(cur)) {
                if (dist[next] == -1) {
                    dist[next] = dist[cur] + 1;
                    queue.add(next);
                }
            }
        }

        int max = 0;
        for (int d : dist) max = Math.max(max, d);

        int answer = 0;
        for (int d : dist) if (d == max) answer++;

        return answer;
    }
}

시간복잡도: O(N + M) — 인접 리스트 구성 O(M), BFS 순회 O(N + M),
공간복잡도: O(N + M) — 인접 리스트와 dist 배열.