[BAEKJOON] 효율적인 해킹

---

풀이 방법

1. a → b 단방향 그래프 생성, 방문 카운트용 int형 answer 일차원 배열 생성

2. 모든 컴퓨터를 시작 지점으로 설정하여 각각의 경로 찾아갈 때마다 visited 배열 초기화

3. 해킹 가능한 컴퓨터 순회 돌면서 방문하지 않았다면 bfs 탐색

4. bfs 내부에서 해킹 가능한 컴퓨터를 만났다면 현재 컴퓨터 번호(=index)에 +1

5. 한 번에 해킹 가능한 최댓값을 찾아서 최댓값과 카운트가 같은 컴퓨터 번호 출력

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

public class Main {
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] answer;
    static boolean[] visited;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

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

        visited = new boolean[N+1];
		answer = new int[N+1];

        for (int i=1; i<=N; i++) {
            visited = new boolean[N+1];
            bfs(i);
        }
        int max = Arrays.stream(answer).max().getAsInt();
        for (int i=0; i<answer.length; i++) {
            if (answer[i] == max) {
            	sb.append(i + " ");
            }
        }
        System.out.println(sb.toString());
    }

    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;
                    answer[computer]++;
                    q.offer(computer);
                }
            }
        }
    }

}

[출처]

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

1325번: 효율적인 해킹