[programmers] 가장 먼 노드

programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int[] dist = new int[n+1];
		boolean[][] mat = new boolean[n + 1][n + 1];
		for(int[] pair : edge) {
			mat[pair[0]][pair[1]] = mat[pair[1]][pair[0]] = true;
		}
		Queue<Integer> q = new LinkedList<>();
		q.offer(1);

		int maxDist = 0;
		while(!q.isEmpty()) {
			int i = q.poll();
			for(int j = 2; j<=n; j++) {
				if(dist[j] == 0 && mat[i][j]) {
					dist[j] = dist[i] + 1;
					q.add(j);
					maxDist = Math.max(maxDist, dist[j]);
				}
			}
		}

		int cnt = 0;
		for(int d : dist) {
			if(maxDist == d) {
				cnt++;
			}
		}

        return cnt;
    }
}