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

- 참고 : programmers.co.kr/learn/courses/30/lessons/49189?language=java

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

 

 

- bfs 문제

- bfs를 돌고 각 지점까지의 최단 거리를 계산하고 해당 값의 최대값 갯수를 세면 된다.

 

 

import java.util.*;
import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        int[] d = new int[n+1];
        boolean[] visited = new boolean[n+1];
        ArrayList<Integer>[] adj = new ArrayList[edge.length];
        for(int i=1; i<=n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for(int i=0; i<edge.length; i++) {
            int V1 = edge[i][0];
            int V2 = edge[i][1];
            adj[V1].add(V2);
            adj[V2].add(V1);
        }
        Queue<Integer> q = new LinkedList();
        q.add(1);
        d[1] = 1;
        visited[1] = true;
        while(!q.isEmpty()) {
            int num = q.poll();
            for(int i=0; i< adj[num].size(); i++) {
                int nNum = adj[num].get(i);
                if(!visited[nNum]) {
                    q.add(nNum);
                    visited[nNum] = true;
                    d[nNum] = d[num] + 1;
                }
            }
        }
        int answer = 0;
        int max = 0;
        for(int i=1; i< d.length; i++) {
            // max = Math.max(max, d[i]);
            if(max < d[i]) {
                max = d[i];
                answer = 1;
            }
            else if(max == d[i]) answer++;
        }
        return answer;
    }
}