백준 6118번 : 숨바꼭질 java

이 문제는 1번 정점에서 탐색을 시작하여 1번 정점에서 다른 정점에 이르기까지 얼마의 시간이 걸리는지 찾는 문제입니다.

위의 사진은 이 문제에서 힌트로 나와 있는 그림입니다.

이 그림과 같이 1번 정점을 기준으로 가장 멀리 떨어져 있는 정점들을 찾으면 됩니다.

이 그림에서는 4, 5, 6이 1에서 거리가 2로 가장 먼 정점들입니다.

그리고 거리가 같을 때는 정점의 번호가 가장 작은 정점에 숨으므로 숨어야 하는 정점은 4이고 거리는 2, 이 헛간과 같은 거리에 있는 헛간의 수는 3개입니다.

---

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

public class Main {
    static int N;
    static List<List<Integer>> l = new ArrayList<>();
    static boolean[] visited;
    static int[] lenArray;
    static int maxLen = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        visited = new boolean[N+1];
        lenArray = new int[N+1];
        for(int i = 0; i<=N; i++)
            l.add(new ArrayList<>());

        while(M-->0){
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            l.get(A).add(B);
            l.get(B).add(A);
        }

        bfs();

        int maxIdx = 0;
        int maxCnt = 0;
        for(int i = 1; i<=N; i++)
            if(lenArray[i] == maxLen){
                if(maxIdx == 0)
                    maxIdx = i;
                maxCnt++;
            }

        System.out.println(maxIdx+" "+maxLen+" "+maxCnt);
    }

    static void bfs(){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(1, 0));
        visited[1] = true;

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

            maxLen = Math.max(maxLen, a.len);
            lenArray[a.vertex] = a.len;

            for(int i = 0; i<l.get(a.vertex).size(); i++){
                int nextV = l.get(a.vertex).get(i);

                if(visited[nextV])
                    continue;

                q.offer(new Node(nextV, a.len+1));
                visited[nextV] = true;
            }
        }
    }
}
class Node{
    int vertex, len;

    Node(int vertex, int len){
        this.vertex = vertex;
        this.len = len;
    }
}

bfs를 이용하면 쉽게 해결하실 수 있는 문제입니다.