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

//알고리즘

1. 그래프 탐색

 

2. 주어진 간선으로 인접리스트를 생성

 

3. 방문배열

 ->방문배열을 int배열로 만들어 1부터 시작하여 도달할 수 있는 거리를 저장한다.

 -> 이미 방문한 노드는 0이 아님

 -> 시작점은 -1로 세팅해야 함

 

4. 방문배열의 최대값을 찾고 정답을(가장 먼 노드들)찾음

import java.util.*;
class Solution {
    ArrayList<Integer>[] list;
    int[] v;
    class Point{
        int r,cnt;
        
        public Point(int r,int cnt){
            this.r = r;
            this.cnt = cnt;
        }
    }
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        list = new ArrayList[n+1];
        v = new int[n+1];
        
        for(int i=1; i<= n; i++){
            list[i] = new ArrayList<>();
        }
        
        int start,end;
        for(int i = 0; i< edge.length; i++){
            start = edge[i][0];
            end = edge[i][1];
            
            list[start].add(end);
            list[end].add(start);
        }
        
        bfs(1,1);
        int max = -1;
        for(int i = 1; i <= n; i++){
            if(max < v[i]) max = v[i];
        }
        
        for(int i = 1; i <= n; i++){
            if(max == v[i]) answer++;
        }
        
        
        return answer;
    }
    
    public void bfs(int idx, int len){
        
        Queue<Point> q = new LinkedList<>();
        v[idx] = -1;
        q.add(new Point(idx,len));
        
        Point p = null;
        while(!q.isEmpty()){
            p = q.poll();
            int size = list[p.r].size();
            for(int i = 0; i<size; i++){
                if(v[list[p.r].get(i)] != 0) continue;
                v[list[p.r].get(i)] = p.cnt;
                q.add(new Point(list[p.r].get(i),p.cnt+1));
            }
            
        }      
       
    }
}