[ 프로그래머스 / JAVA / Level 3 ] 가장 먼 노드

제출한 코드

import java.io.*;
import java.util.*;

class Solution {
    static Node[] node;
    
    static class Node{
        List<Integer> linked = new ArrayList<>();
    }
    
    public int solution(int n, int[][] edge) {
    	// Node 초기값 세팅
        node = new Node[n+1];
        for(int i = 1 ; i <= n ; i++){
            node[i] = new Node();
        }
        // 간선 정보 저장
        for(int i = 0 ; i < edge.length;i++){
            int u = edge[i][0];
            int v = edge[i][1];
            
            node[u].linked.add(v);
            node[v].linked.add(u);
        }
        
        int answer = bfs(n);
          
        return answer;
    }
    
    private static int bfs(int n){
        boolean[] v = new boolean[n+1];
        Deque<int[]> q = new ArrayDeque<>();
        
        int maxLen = 0; // 가장 먼 거리
        int cnt = 0; // 개수
        
        // root 노드 1에서 시작
        v[1] = true;
        q.add(new int[] {1,0});
        
        while(!q.isEmpty()){
            int[] cur = q.poll();
            
            // 거리값이 갱신되는 경우
            if(cur[1] > maxLen){
                maxLen = cur[1];
                cnt = 1;
            }
            // 개수 추가
            else if(cur[1] == maxLen){
                cnt++;
            }
            
            for(int next : node[cur[0]].linked){
                if(v[next]){
                    continue;
                }
                
                v[next] = true;
                q.add(new int[] {next, cur[1]+1});
            }
        }
        
        return cnt;
    }
}

---

 

 

생각한 로직

1. root node를 시작으로 최대 거리를 bfs로 구한다.

2. 최대 거리가 갱신되는 경우 maxLen 수정 및 cnt 초기화

3. 최대 거리와 동일한 경우 cnt값 증가