가장 먼 노드

---

풀이 방법

노드 별 최단 경로를 구하기 위해 Node 클래스를 만들어서 노드 번호와 1번에서 해당 노드까지의 길이를 가지도록 했다.

bfs 를 이용해서 노드까지의 길이를 비교해서 최댓값일 경우 cnt를 증가시켜주었다.

 

내 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {       
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        boolean[] visited = new boolean[n + 1];
        
        for(int i = 0; i <= n; i++){
            list.add(new ArrayList<Integer>());
        }
        
        for(int i = 0; i < edge.length ;i++){
            list.get(edge[i][0]).add(edge[i][1]);
            list.get(edge[i][1]).add(edge[i][0]);
        }
        
        Queue<Node> q = new LinkedList<>();
        
        q.add(new Node(1, 0));
        int cnt = 0;
        int max = 0;
        
        while(!q.isEmpty()){
            Node node = q.poll();
            
            if(visited[node.index])
                continue;
            
            if(max < node.len){
                cnt = 1;
                max = node.len;
            } else if(max == node.len) {
                cnt++;
            }
            
            visited[node.index] = true;
            
            for(int i = 0; i < list.get(node.index).size(); i++){
                q.add(new Node(list.get(node.index).get(i), node.len + 1));
            }
        }
        
        System.out.println(cnt);
        return cnt;
    }
    
    class Node{
        int index;
        int len;
        
        Node(int index, int len){
            this.index = index;
            this.len = len;
        }
    }
}