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

- 문제

프로그래머스

- 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        
        //답의 개수를 담아줄 answer입니다.
        int answer = 0;
        
        //각 노드가 이동할 수 있는 노드들을 담는 ArrayList<>를 생성합니다.
        ArrayList<ArrayList<Integer>> check = new ArrayList<>();
        
        //각각 노드의 틀을 만들어줍니다.
        for(int i=0; i<=n; i++){
            check.add(new ArrayList<>());
        }
        
        //이제 입력으로 주어진 edge를 순회하며 각 노드간의 연결관계를 기록해줍니다.
        for(int i=0; i<edge.length; i++){
            
            //이번 i의 노드를 연결을 가져옵니다.
            int[] now = edge[i];
            
            //노드는 양방향의 연결관계이므로 앞뒤를 바꾸어 입력해줍니다.
            check.get(now[0]).add(now[1]);
            check.get(now[1]).add(now[0]);
        }
        
        //1과의 거리를 기록할 int[]배열 len을 선언합니다.
        int[] len = new int[n+1];
        
        //int[] 배열이 초기화되는 0을 이용해서 방문 여부를 검사하고 값을 넣어줄 예정이라
        //에러가 발생하지 않게 시작점 1에는 -1을 넣어줍니다.
        len[1] = -1;
        
        //이제 BFS 탐색을 하는데 사용할 Queue 자료구조 q를 선언합니다.
        Queue<Integer> q = new LinkedList<>();
        
        //1번 노드에서 갈 수 있는 노드들을 찾아서 q에 입력해줍니다.
        //한 번에 갈 수 있는 노드들이므로 모두 1의 거리로 표시해줍니다.
        for(int a : check.get(1)){
            q.add(a);
            len[a] = 1;
        }
        
        //거리를 표시할 idx 변수를 선언합니다.
        int idx = 1;
        
        //while을 통해 bfs를 진행합니다. 
        while(!q.isEmpty()){
            
            //이번에 나오는 노드들의 거리는 idx 입니다.
            idx++;
            
            //이번 while문에서 나오는 노드들은 1로부터 모두 같은 거리를 가집니다.
            int size = q.size();
            
            //Queue에서 size만큼만 꺼내서 탐색해줍니다.
            for(int i=0; i<size; i++){
                int now = q.poll();
                
                //now 노드에서 갈 수 있는 노드들 a를 확인해줍니다.
                for(int a : check.get(now)){
                    
                    //만약 아직 도달한 적이 없을 경우
                    //해당 노드에는 idx 거리만큼 떨어져있다고 볼 수 있습니다.
                    //그리고 다시 q를 다음 탐색을 대비합니다.
                    if(len[a]==0){
                        len[a] = idx;
                        q.add(a);
                    }
                }
            }
        }
        
        //while이 끝나는 마지막 반복에는 아무 노드도 없다는 의미
        //즉 이전 while 탐색의 거리가 가장 멀리 떨어진 노드의 거리입니다.
        //따라서 -1을 해줍니다.
        idx--;
        
        //이제 각 노드들을 순회하며 1에서 해당 노드까지의 거리를 확인하며
        //최대 거리인 idx와 같을 경우 answer을 추가해줍니다.
        for(int i=2; i<=n; i++){
            if(idx==len[i]) answer++;
        }
        
        //답을 반환합니다.
        return answer;
    }
}