프로그래머스 - 그래프 - 가장 먼 노드

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

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

 

import java.util.*;
 
public class 가장_먼_노드 {
    public static void main(String[] args) {
        가장_먼_노드 o = new 가장_먼_노드();
        System.out.println(o.solution(6, new int[][]{{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}}));
        //System.out.println(o.solution(2, new int[][]{{1, 2}}));
        //System.out.println(o.solution(4, new int[][]{{4, 3}, {1, 3}, {2, 3}}));
    }
 
    public int solution(int n, int[][] edge) {
        List<List<Integer>> adList = new ArrayList<>();
 
        for(int i=0; i<n+1; i++) {
            adList.add(new ArrayList<>());
        }
 
        for(int i=0; i<edge.length; i++) {
            adList.get(edge[i][0]).add(edge[i][1]);
            adList.get(edge[i][1]).add(edge[i][0]);
        }
 
        return getCountOfDistantNodeByBFS(adList);
    }
 
    private int getCountOfDistantNodeByBFS(List<List<Integer>> adList) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] isVisit = new boolean[adList.size()];
        Integer[] dist = new Integer[adList.size()];
        Arrays.fill(dist, Integer.MAX_VALUE);
 
        q.offer(1);
        dist[1] = 0;
        dist[0] = Integer.MIN_VALUE;
 
        while (!q.isEmpty()) {
            int curNode = q.poll();
            isVisit[curNode] = true;
 
            for(int nextNode : adList.get(curNode)) {
                if(!isVisit[nextNode] && dist[nextNode] > dist[curNode] + 1) {
                    q.offer(nextNode);
                    dist[nextNode] = dist[curNode] + 1;
                }
            }
        }
 
        Arrays.sort(dist);
        int maxValue = dist[dist.length-1];
        int count = 0;
        for(int i=dist.length-1; i>=0; i--) {
            if(dist[i].equals(maxValue)) {
                count++;
            } else {
                break;
            }
        }
 
        return count;
    }
}
 

 

알고리즘

• BFS
• BFS로 모든 노드를 순회한다.
• 이때 최단거리를 찾기위해 다음 노드의 거리가 현 노드의 거리 +1보다 크면 다음 노드의 최단거리를 현 노드의 거리 + 1로 업데이트해준다.
• 최단거리 배열을 정렬하여 가장 큰 값과 같은 값의 갯수를 출력해준다.