가장 먼 노드

주어진 문제는 그래프에서 BFS(너비 우선 탐색)를 활용하여 최단 경로를 계산하고, 1번 노드에서 가장 멀리 떨어진 노드의 수를 계산하는 것입니다. BFS를 사용하면 그래프의 각 노드까지의 최단 경로를 쉽게 구할 수 있다.

풀이 과정

1. 그래프 초기화
   • n개의 노드를 표현하기 위해 인접 리스트를 사용합니다.
   • 간선 정보를 기반으로 양방향 그래프를 생성합니다.
2. BFS를 이용한 최단 거리 계산
   • 1번 노드에서 시작하여 BFS를 수행합니다.
   • 방문한 노드의 거리를 기록하며 탐색합니다.
3. 가장 멀리 떨어진 노드 찾기
   • BFS 결과에서 최댓값을 찾고, 해당 거리를 가진 노드의 개수를 세어 반환합니다.

import java.util.*;

public class FarthestNode {
    public int solution(int n, int[][] edge) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> distances = new HashMap<>();

        for (int i = 1; i <= n; i++) graph.put(i, new ArrayList<>());

        for (int[] node : edge) {
            graph.get(node[0]).add(node[1]);
            graph.get(node[1]).add(node[0]);
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1, 0});
        distances.put(1, 0);
        Integer max = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int node = current[0];
            int distance = current[1];
            max = Math.max(max, distance);
            for (int neighbor : graph.get(node)) {
                if (distances.containsKey(neighbor)) continue;
                queue.add(new int[]{neighbor, distance + 1});
                distances.put(neighbor, distance + 1);
            }
        }

        int answer = 0;
        for (Map.Entry<Integer, Integer> entry : distances.entrySet()) {
            if (entry.getValue().equals(max)) answer++;
        }

        return answer;
    }
}