[알고리즘] 프로그래머스 가장 먼 노드

https://school.programmers.co.kr/learn/courses/30/lessons/49189#

프로그래머스

코드 설명

정점, 간선이 주어진 입력 배열에서 인접리스트를 만들어서
BFS 로 가장 먼 거리를 구했다.DFS와 BFS는 많이 풀면 풀수록 다양한 개념들이 많이 나온다.
다 이해했다고 생각하지말고 계속 여러번 반복해서 풀어봐야겠다.

import java.util.*;

class Solution {
    
    static int[] visited;
    static ArrayList<ArrayList<Integer>> al;
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        al = new ArrayList<>();
        visited = new int[n + 1];
        
        // 정점이 6개까지 있으므로 0~6으로 선언해야되는거 주의
        for(int i = 0; i <= n; i++)
            al.add(new ArrayList<Integer>());
        
        for(int i = 0; i < edge.length; i++){
            al.get(edge[i][0]).add(edge[i][1]);
            al.get(edge[i][1]).add(edge[i][0]);
        }
        
        BFS(1);
        
        Arrays.sort(visited);
        
        int max = visited[n];
        
        for(int i = 0; i <= n; i++){
            if(max == visited[i])
                answer++;
        }
        
        return answer;
    }
    
    public static void BFS(int V){
        Queue<Integer> qu = new LinkedList<>();
        
        qu.add(1);
        visited[1] = 1;
        
        while(!qu.isEmpty()){
            int cur = qu.poll();
            
            for(int next : al.get(cur)) {
                
                if(visited[next] == 0){
                    visited[next] = visited[cur] + 1;
                    qu.add(next);
                }
            }
        }
    }
}