[Do It! 코딩테스트 자바편(김종관)] 문제 047(백준 1325번)

난이도

발상만 떠오르면 쉽게 구현할 수 있지만… 안 떠올라서 교재 힌트를 봤다. 아이디어를 얻은 후에 이를 구현하는 것은 쉬웠다.

문제

효율적인 해킹 (백준: 1325번)

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static ArrayList<Integer>[] list;
    static boolean[] visited;
    static int[] trust;

    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());
        m = Integer.parseInt(st.nextToken());
        list = new ArrayList[n + 1];
        for (int i = 1; i < list.length; i++) {
            list[i] = new ArrayList<Integer>();
        }
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list[s].add(e);
        }

        trust = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            visited = new boolean[n + 1];
            bfs(i);
        }

        int max = 0;
        for (int i = 1; i < trust.length; i++) {
            if (trust[i] > max) {
                max = trust[i];
            }
        }
        for (int i = 1; i < trust.length; i++) {
            if (trust[i] == max) {
                System.out.print(i + " ");
            }
        }

    }

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

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int tmp : list[node]) {
                if (!visited[tmp]) {
                    queue.add(tmp);
                    visited[tmp] = true;
                    trust[tmp]++;
                }
            }
        }
    }

}