1 번부터 가장 먼 거리의 노드의 개수 ? 배열에서 최대값의 개수 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

 

 

BFS 로 풀면 된다.

 

가장 먼 노드들의 전체 개수를 조회를 하는 방법이 무엇이 있을까를 고민을 했고 단순하게 리스트를 이용하는게 좋아 보였다.

 

distance 배열이 주어졌을때 최대값의 개수를 어떻게 구할까 ?

 

Arrays.stream 을 이용하자.

 

 int maxDistance = Arrays.stream(distance).max().getAsInt();
 
long count = Arrays.stream(distance).filter(d -> d == maxDistance).count();

 

 

class Solution {
    public int solution(int n, int[][] edge) {

        boolean[] visited = new boolean[n+1];

        List<List<Integer>> way = new ArrayList<>();
        for(int i =0 ; i < n+1 ; i++) {
            way.add(new ArrayList<>());
        }

        for(int[] item : edge) {
            int left = item[0];
            int right = item[1];
            way.get(left).add(right);
            way.get(right).add(left);
        }
//        System.out.println(way);

        int[] distance = new int[n+1];  // 1번 노드로부터의 거리를 저장할 배열

        // bfs
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        visited[1] = true;
        while (!q.isEmpty()){
            int cuurNode = q.poll();
            for(int nextNode : way.get(cuurNode)) {
                if(!visited[nextNode]){
                    visited[nextNode] = true;
                    q.offer(nextNode);
                    distance[nextNode] = distance[cuurNode] + 1;
                }
            }
        }

        // return number of node , which max far from number 1 :
        int maxDistance = Arrays.stream(distance).max().getAsInt();
        long count = Arrays.stream(distance).filter(d -> d == maxDistance).count();

        return (int) count;
    }

    
}