[BJ] 1325 효율적인 해킹 Java

백준 1325 효율적인 해킹

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

1325번: 효율적인 해킹

아이디어

• 컴퓨터를 노드, 연결된 신뢰도를 에지라고 생각하고 BFS/DFS를 수행하면 된다
• 탐색을 수행하면서 해킹할 수 있는 컴퓨터, 즉 신뢰도가 있는 컴퓨터라면 개수를 카운팅 해준다
• 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력해야하니 BFS/DFS를 모두 수행한 후 배열에 있는 값 중 최대값을 구하여
• 해당 값에 해당하는 인덱스를 출력해주면 된다

코드

package baekjoon;
import java.util.*;
import java.io.*;

class BJ1325 {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] hacks;
    static boolean[] visited;
    static int computers, line;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        computers = Integer.parseInt(st.nextToken());
        line = Integer.parseInt(st.nextToken());

        // 필요한 그래프와 해킹된 배열 초기화
        for (int i=0; i<=computers; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프 만들기
        for (int i=0; i<line; i++) {
            st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
        }

        visited = new boolean[computers+1];
        hacks = new int[computers+1];

        // 컴퓨터마다 BFS를 수행해서 해킹가능 컴퓨터 구함
        for (int i=1; i<=computers; i++) {
            visited = new boolean[computers+1];
            BFS(i);
        }
        int max = Arrays.stream(hacks).max().getAsInt();
        for (int i=0; i<hacks.length; i++) {
            if (hacks[i] == max) {
                System.out.print(i + " ");
            }
        }

    }

    public static void BFS(int index) {
        Queue<Integer> q = new LinkedList<>();
        visited[index] = true;
        q.offer(index);

        while (!q.isEmpty()) {
            int cv = q.poll();
            for (int computer : graph.get(cv)) {
                if (!visited[computer]) {
                    visited[computer] = true;
                    hacks[computer] += 1;
                    q.offer(computer);
                }
            }
        }
    }
}

Scanner로 입력받은 것과 BufferedReader을 사용한 코드의 시간 차이

아래 (Scanner) 위(BufferedReader)