풀기 전

간선의 비용이 모두 1이고
가장 먼 노드를 찾으면 되는 것이므로

가장 먼저 떠올랐던 것은 BFS 였다.
다만 가장 거리가 먼 노드를 찾기 위해
지나온 경로의 수를 queue 의 깊이가 깊어질 때마다 하나씩 증가시켰다.

그러기 위해서 Node 란 클래스를 활용했다.

정답 코드

import java.util.*;

class Node{
    int start;
    int countNumber;
    
    public Node(int start,int countNumber){
        this.start = start;
        this.countNumber = countNumber;
    }
}

class Solution {
    
    public int solution(int n, int[][] edge) {
        
        List<Integer> []lists=new ArrayList[n+1];
        
        for(int i=0;i<=n;i++){
            lists[i]=new ArrayList<>();
        }
        
        for(int i=0;i<edge.length;i++){
            lists[edge[i][0]].add(edge[i][1]);
            lists[edge[i][1]].add(edge[i][0]);
        }
        
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(1,0));
        
        boolean isUsed[]=new boolean[n+1];
        List<Node> lastNode = new ArrayList<>();
        isUsed[1]=true;
        
        while(!queue.isEmpty()){
            
            Node currentNode = queue.poll();
            int currentStart = currentNode.start;
            
            boolean isLastNode = true;
            for(int dest: lists[currentStart]){
                if(!isUsed[dest]){
                    queue.add(new Node(dest,currentNode.countNumber+1));
                    isUsed[dest]=true;
                    isLastNode=false;
                }
            }
            
            if(isLastNode){
                lastNode.add(currentNode);
            }
            
            
        }
        
        lastNode.sort(new Comparator<Node>(){
            @Override
            public int compare(Node o1,Node o2){
                return o1.countNumber-o2.countNumber;
            }
        });
        
       
        int answer = 0;
        int max = -3;
        for(int i=0;i<lastNode.size();i++){
            
            if(i==0){
                answer+=1;
                if(max<lastNode.get(i).countNumber){
                    max = lastNode.get(i).countNumber;
                }
            }
            
            else{
                if(max == lastNode.get(i).countNumber){
                    answer++;
                }
                else{
                    max = lastNode.get(i).countNumber;
                    answer = 1;
                }
            }
            
            
        }
        
        return answer;
                 
    }
}

배운 풀이

1) 굳이 지금까지 지나온 거리를 class Node 에 저장할 필요 없이 int [] 값으로 커버 가능하다. 옛날에도 적었었던 내용인데 적용 할 생각을 못했다.

클래스를 생성할 때는 int[] 로 어느정도 커버가 가능한지 먼저 생각하는 습관을 들여보자.

2) 아니면 그냥 distMax[] 라는 배열을 넣고 거기다가 지나온 길을 입력하되
그 중에서 최댓값만 선택하면 된다.

사실 정렬도 필요 없다.

더 복잡하고 효율적이지 않게 푼 것 같아서 아쉽다.