[BFS] 프로그래머스 - 가장 먼 노드 (자바)

시작점 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return.

 

BFS로 푸는 문제.

 

내가 까먹을까봐 기록함.

 

문제 링크

풀이 출처 (설명 잘 돼있음. 문제는 내 이해력;;)

 

풀이

import java.util.*;

class Solution {
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        int[] distance = new int[n + 1];
        boolean[] visited = new boolean[n + 1];
        
        for(int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for(int i = 0; i < edge.length; i++) {
            graph.get(edge[i][0]).add(edge[i][1]);
            graph.get(edge[i][1]).add(edge[i][0]);
        }
        
        visited[1] = true;
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        while(!q.isEmpty()) { // 2 ~ n까지 도착하는 경로 구하기
            int now = q.poll();
            ArrayList<Integer> node = graph.get(now);
            for(int i = 0; i < node.size(); i++) {
                if(visited[node.get(i)] == false) {
                    q.add(node.get(i));
                    visited[node.get(i)] = true;
                    distance[node.get(i)] = distance[now] + 1;
                }
            }
        }
        
        Arrays.sort(distance);
        int max = distance[distance.length - 1];
        for(int i = 0; i < distance.length; i++) {
            if(max == distance[i]) answer++;
        }
        
        return answer;
    }
}