[프로그래머스] LV3 가장 먼 노드(JAVA)

문제

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

문제풀이

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        List<ArrayList<Integer>> graph = new ArrayList<>();
        for(int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for(int[] e : edge) {
            int num1 = e[0];
            int num2 = e[1];
            graph.get(num1).add(num2);
            graph.get(num2).add(num1);
        }
        
        int[] answer = new int[n + 1];
        Arrays.fill(answer, n + 1);
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        answer[1] = 0;
        
        while(!queue.isEmpty()) {
            int node = queue.poll();
            for(int next : graph.get(node)) {
                if(answer[next] > answer[node] + 1) {
                    answer[next] = answer[node] + 1;
                    queue.offer(next);
                }
            }
        }

        Arrays.sort(answer);
        int max = answer[answer.length-2];
        
        int count = 0;
        for(int i = answer.length-2; i >= 0; i--) {
            if(answer[i] != max) {
                break;
            }
            count++;
        }
        return count;
    }
}

 

1. 인접리스트를 통해서 그래프를 그려준다.

2. bfs를 돌면서 1부터 각 노드까지의 최단거리를 업데이트 해준다.

3. 거리가 가장 먼 값과 같은 노드가 몇 개 인지 구하면 끝