[백준] 6118번. 숨박꼭질(JAVA)

문제

https://www.acmicpc.net/problem/6118

---

풀이(19분)

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

public class Main {

    static int n, m;
    static List<List<Integer>> graph;
    static int[] counts;
    static Queue<Node> queue = new LinkedList<>();

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

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        counts = new int[n + 1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int aI = Integer.parseInt(st.nextToken());
            int bI = Integer.parseInt(st.nextToken());
            graph.get(aI).add(bI);
            graph.get(bI).add(aI);
        }

        // 1번 노드에서 시작
        queue.add(new Node(1, 0));
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (int next : graph.get(cur.end)) {
                if (!visited[next]) {
                    visited[next] = true;
                    counts[next] = cur.cost + 1;
                    queue.add(new Node(next, cur.cost + 1));
                }
            }
        }

        // 가장 먼 노드 찾기
        int maxDist = 0;
        int minIdx = 0;
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (counts[i] > maxDist) {
                maxDist = counts[i];
                minIdx = i;
                count = 1;
            } else if (counts[i] == maxDist) {
                count++;
            }
        }

        System.out.println(minIdx + " " + maxDist + " " + count);
    }

    static class Node {
        int end, cost;

        public Node(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }
    }
}

---

문제 풀이 전략

 

bfs를 통해 인접한 곳들을 탐색해 가며 이에 대한 최솟값을 기록해 두는 것이다.

-> 최솟값을 기록하는 것으로 방문배열을 처리할 수 있다!

 

최종적으로 모든 점을 다시 탐색하며 문제 조건에 맞는 출력을 하면 된다.