[프로그래머스 / 그래프] 가장 먼 노드 (java)

[문제 접근]

연결 리스트로 그래프를 구현한 뒤, bfs로 순회하며 간선의 개수를 센다. (최소 간선 경로 이므로 bfs)

 

[코드]

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        //bfs
        ArrayList<ArrayList<Integer>> graph = new <ArrayList<Integer>> ArrayList();
        Queue<Integer> queue = new LinkedList<>();
        int[] depth = new int[n+1];
        
        Arrays.fill(depth, -1);
        
        for(int i = 0; i < n + 1; i++){
            graph.add(new ArrayList<Integer>());
        }
        
        //무방향 그래프이므로 양쪽 다 추가
        for(int i = 0; i < edge.length; i++){
            int m = edge[i][0];
            int k = edge[i][1];
            graph.get(m).add(k);
            graph.get(k).add(m);
        }
        
        //1번 노드
        queue.add(1);
        depth[1] = 0;
        int u = 0; // (u, v)
        
        //bfs
        while(!queue.isEmpty()){
            u = queue.poll();
            for(int v: graph.get(u)){
                if(depth[v] == -1){
                    depth[v] = depth[u] + 1;
                    queue.add(v);
                }
            }
        }
        
        //find max
        int max = -1;
        int count = 0; //개수
        for(int i = 0; i < depth.length; i++){
            if(max < depth[i]){
                max = depth[i];
                count = 1;
            } else if(max == depth[i])
                count++;
        }
        answer = count;
        return answer;
    }
    
}

 

[참고]

https://heedipro.tistory.com/233

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