백준 숨바꼭질(1697)

백준 숨바꼭질

풀이

bfs를 돌려서 깊이를 세어서 중복되는 위치의 수와 가장 낮은 위치를 출력해 주기만 하면되는 전형적인 그래프 문제

첫 제출은 2차원 배열을 사용해서 그런지 메모리 초과가 나왔는데 ArrayList로 해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int depth[];
    public static boolean visited[];
    public static ArrayList<ArrayList<Integer>> map = new ArrayList<>();
    public static int max;

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

        int nodeNum = Integer.parseInt(st.nextToken());
        int edgeNum = Integer.parseInt(st.nextToken());

        visited = new boolean[nodeNum+1];
        depth = new int[nodeNum+1];

        for(int i=0; i<=nodeNum; i++) map.add(new ArrayList<>());

        for(int i=0; i<edgeNum; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            map.get(a).add(b);
            map.get(b).add(a);
        }

        bfs(1);

        ArrayList<Integer> list = new ArrayList<>();

        int dup = 0;
        for(int i=1; i<depth.length; i++){
            if(max == depth[i]){
                list.add(i);
                dup++;
            }
        }

        Collections.sort(list);
        int minIdx = list.get(0);

        System.out.print(minIdx + " " + depth[minIdx] + " " + dup);

    }

    public static void bfs(int start){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        depth[start] = 0;

        while(!queue.isEmpty()){
            int cur = queue.poll();

            for(int num : map.get(cur)){
                if(num!=0 && !visited[num]){
                    queue.add(num);
                    visited[num] = true;
                    depth[num] = depth[cur]+1;
                    max = depth[num];
                }
            }

        }

    }


}