[백준 01325] 효율적인 해킹 [Java]

문제

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

---

 

 

풀이

단방향 그래프가 주어질 때, 가장 많은 정점을 방문할 수 있는 시작 정점을 찾는 문제다.

A가 B를 신뢰할 때 B가 해킹 당하면 A도 해킹 당한다. 신뢰 관계에 대한 단방향 그래프를 구성하자.

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

public class Main {
    static List<List<Integer>> graph = new ArrayList<>();
    static int N;
    static int[] cnt
    public static void main(String[] args) throws IOException {
        // Init
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // Input
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        cnt = new int[N + 1];
        for (int i = 0; i <= N; ++i) {
            graph.add(new ArrayList<>());
        }
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            final int a = Integer.parseInt(st.nextToken());
            final int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
        }

어떤 정점에서 출발해야 가장 많은 정점을 방문하는지 알 수 없기 때문에, 시작 정점이 1 ~ N인 경우에 대해 전부 탐색해야 한다.

        // Solve
        for (int i = 1; i <= N; ++i) {
            bfs(i);
        }

bfs를 하며, 방문하는 정점마다 cnt값을 증가시켜 영향을 받는 정점의 수를 세주자.

    private static void bfs(int start) {
        boolean[] visited = new boolean[N + 1];
        visited[start] = true;
        Deque<Integer> queue = new ArrayDeque<>(List.of(start));

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : graph.get(cur)) {
                if (!visited[next]) {
                    ++cnt[next];
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }
    }

그래프에 대한 탐색이 모두 끝난 후 cnt에서 최댓값을 찾고, 동일한 최댓값을 가진 정점을 모두 찾아서 정렬 후 출력하자.

        int max = 0;
        for (int num : cnt) {
            max = Math.max(max, num);
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 1; i <= N; ++i) {
            if (cnt[i] == max) {
                res.add(i);
            }
        }
        Collections.sort(res);

        // Output
        System.out.println(res.toString().replaceAll("[\\\\[|\\\\],]", ""));
    }
}

---

소스코드

보기