가장 먼 노드

문제 정보

• 프로그래머스 Lv.3
• 그래프
• 문제 링크

풀이

완전 탐색으로 모든 노드와의 거리를 구하면 되는 문제다.

우선 edge[][]를 돌면서 인접 리스트로 그래프를 구성하고, 1번 노드부터 시작해서 완전 탐색(BFS) 해준다.

노드에 도착할 때마다 거리를 갱신해주고, 거리는 $n-1\text{번 노드까지의 거리}+1$로 계산한다.

이후 가장 먼 거리(max)를 구하고, 거리가 max와 동일한 노드의 개수를 반환하면 된다.

코드

import java.util.*;
 
class Solution {
    public int solution(int n, int[][] edge) {
	    // 인접 리스트로 그래프 구현
        List<List<Integer>> adj = new ArrayList<>();
        
        for (int i = 0; i < n + 1; i++)
            adj.add(new ArrayList<>());
        
        for (int[] e : edge) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);   
        }
        
        // 1번 노드로부터의 거리 배열 초기화
        int[] dist = new int[n + 1];
        Arrays.fill(dist, 0);
        
        // BFS를 위한 큐 및 isVisited 배열
        Deque<Integer> queue = new ArrayDeque<>();
        boolean[] isVisited = new boolean[n + 1]; // 노드 방문 확인용
        queue.add(1);
    
	    // BFS
        while(!queue.isEmpty()) {
            int cur = queue.pollFirst(); 
            isVisited[cur] = true;
            
            for (int next : adj.get(cur)) {
                if (!isVisited[next] && !queue.contains(next)) {
                    dist[next] = dist[cur] + 1;
                    queue.addLast(next);
                }
            }
        }
        
        // 가장 먼 거리 탐색
        int max = (int) Arrays.stream(dist).max().getAsInt();
        
        // 가장 멀리 떨어진 노드 개수 반환
        return (int) Arrays.stream(dist)
            .filter(d -> d == max)
            .count();
    }
}