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

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/49189

🌱 문제

• 1번 노드로부터 가장 멀리 떨어진 노드가 몇개인지 구하는 문제이다.

🌱 풀이

• 간단한 bfs 문제였다.
• 1번 노드를 시작으로 bfs를 돌리면서 1번 노드로 부터의 거리를 dist[] 배열에 기록해주었다.
• 최단경로를 구하는 문제이므로 bfs를 돌리면 바로 나온다.
• bfs가 끝난 후 dist[]값이 max인 갯수를 세어준다.

🌱 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        int dist[]= new int[n+1];
        ArrayList<Integer>[] edges = new ArrayList[n+1];
        for(int i=0; i<=n; i++){
            edges[i]=new ArrayList<Integer>();
        }
        for(int i=0; i<edge.length; i++){
            int from=edge[i][0]; 
            int to=edge[i][1];
            edges[from].add(to);
            edges[to].add(from);
        }
        // for(int i=1; i<=n; i++){
        //     for(int j=0; j<edges[i].size(); j++){
        //         System.out.print(edges[i].get(j)+" ");
        //     }
        //     System.out.println();
        // }
        boolean visit[] = new boolean[n+1];
        Queue<Integer> q = new ArrayDeque<Integer>();
        q.add(1);
        visit[1]=true;
        while(!q.isEmpty()){
            int cur= q.poll();
            for(int i=0; i<edges[cur].size(); i++){
                int next=edges[cur].get(i);
                if(visit[next]==false){
                    visit[next]=true;
                    dist[next]=dist[cur]+1;
                    q.add(next);
                }
            }
        }
        int max=0;
        for(int i=1; i<=n; i++){
            max=Math.max(max,dist[i]);
            System.out.println("dist: "+dist[i]);
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=1; i<=n; i++){
            if(dist[i]==max)
                list.add(i);
        }
            
        
        

        
        return list.size();
    }
}