[백준 1167] Java - bfs 여러번 사용

🔵bfs 2번 탐색

1. 임의의 정점에서 bfs > 거리 제일 먼게 가장 끝에 있는 정점임 >> 가장 끝에 있는 정점 구하기

2. 가장 끝에 있는 정점에서 bfs 탐색 > 두 점 사이 중 가장 긴 거리 구하기 가능!

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    static int V; // 정점 개수
    static int[] dist; // 거리 저장
    static ArrayList<Node>[] adjList; // 인접노드 저장
    static boolean[] visited; // 방문여부 저장
    
    static class Node{
        int to;
        int w;

        public Node(int to, int w){
            this.to = to;
            this.w = w;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 정점 개수 입력받기
        V = Integer.parseInt(br.readLine());
        
        //초기설정
        dist = new int[V+1]; // 정점번호 1번부터 시작
        Arrays.fill(dist, 0);
        visited = new boolean[V+1];
        adjList = new ArrayList[V+1];
        for(int i=1; i<=V; i++){
            adjList[i] = new ArrayList<>();
        }
        
        // 간선 정보 입력받기
        for(int i=1; i<=V;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            
            while(true){
                int b = Integer.parseInt(st.nextToken());
                if(b==-1){
                    break;
                }
                int c = Integer.parseInt(st.nextToken());
                adjList[a].add(new Node(b, c));
            }
        }
        
        //bfs 임의의 정점부터 탐색 > 가장 끝에 있는 정점 구하기
        bfs(1);

        //가장 끝에 있는 정점에서 거리 탐색 > 최댓값 구하기
        //dist 제일 큰 값인 정점 구하기
        int max = 1;
        for(int i=2; i<=V;i++){
            //System.out.print(dist[i]+" ");
            if(dist[max] < dist[i]){
                max = i;
            }
        }
        
        //dist, visited 배열 초기화
        Arrays.fill(dist, 0);
        Arrays.fill(visited, false);
        bfs(max);

        //결과 출력 > dist 정렬 후 제일 마지막(최댓값) 출력
        Arrays.sort(dist);
        System.out.println(dist[V]);
    } //main

    //bfs
    static void bfs(int start){
        ArrayDeque<Node> q = new ArrayDeque<>();
        dist[start] = 0;
        q.offer(new Node(start, 0));
        visited[start] = true;

        while(!q.isEmpty()){
            Node current = q.poll();

            for(Node next : adjList[current.to]){
                if(visited[next.to]){
                    continue;
                }
                visited[next.to] = true;
                q.offer(next);
                dist[next.to] = dist[current.to] + next.w;
            }
        } //while문
    }
}