프로그래머스 가장 먼 노드

 

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

 

풀이  :

① BFS를 이용해 1부터 특정 노드까지의 경로를 탐색 후 거리를 저장

② 탐색한 거리 중 가장 먼 거리의 갯수를 세어 반환

 

2021.09.19 - [알고리즘/알고리즘] - 너비 우선 탐색 Breath-first Search BFS

 

구현JAVA

import java.util.*;

class Solution {
   	public int solution(int n, int[][] edges) {
        
		  // 방문여부를 저장할 배열
        boolean[] isVisited = new boolean[n+1];
        // 지점별 1과의 거리를 저장할 배열
        int[] distance = new int[n+1];
        //edges를 인접리스트로 변환
        List<List<Integer>> vertex = new ArrayList<>(n);
        for(int i = 0; i<=n; i++){
            vertex.add(new ArrayList<>());
        }

        System.out.println(vertex.size());

        for(int[] edge: edges){
           vertex.get(edge[0]).add(edge[1]);
           vertex.get(edge[1]).add(edge[0]);
        }
        // 경로를 저장할 queue
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1); isVisited[0] = true; isVisited[1] = true;

        while(!queue.isEmpty()){
            int now = queue.poll();
            for(int v : vertex.get(now)){
                if(!isVisited[v]){
                    distance[v] = distance[now]+1;
                    isVisited[v] = true;
                    queue.add(v);
                }
            }
        }
        int max = Arrays.stream(distance).max().getAsInt();
        return (int) Arrays.stream(distance).filter(a -> a==max).count();
	}
}