백준 1325 효율적인 해킹 JAVA

문제

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

---

입출력

---

예제

---

태그

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

풀이

• bfs를 이용한 풀이
• 1번부터 N번까지 모든 번호의 컴퓨터를 대상으로 bfs를 진행하고 해당 번호의 컴퓨터를 해킹했을 때 몇 개의 컴퓨터를 해킹할 수 있는지를 세서 arr 배열에 저장한다.
• bfs를 돌 때 이미 해킹된 컴퓨터라면 넘어간다.(visited배열 값을 true로 설정)

---

코드

정답 코드

/**
 * 1325_효율적인 해킹
 *
 * bfs를 이용한 풀이
 * 1번부터 N번까지 모든 번호의 컴퓨터를 대상으로 bfs를 진행하고 해당 번호의 컴퓨터를 해킹했을 때
 * 몇 개의 컴퓨터를 해킹할 수 있는지를 세서 arr 배열에 저장한다.
 * bfs를 돌 때 이미 해킹된 컴퓨터라면 넘어간다.(visited배열 값을 true로 설정)
 */

public class P_1325 {
    static int N, M;
    static ArrayList<ArrayList<Integer>> graph; // 해킹할 수 있는 컴퓨터의 인접 리스트
    static int[] arr; // 각 index별 컴퓨터 해킹할 수 있는 개수 저장 배열
    static boolean[] visited; // 방문처리를 위한 배열
    static int max = Integer.MIN_VALUE; // 최대값을 구하기 위한 변수

    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());
        arr = new int[N+1];

        // 인접 리스트 구현
        graph = new ArrayList<>();
        for (int i = 0; i < N + 1; 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(b).add(a);
        }

        // bfs 진행
        for (int i = 1; i <= N; i++) {
            // 방문처리 초기화
            visited = new boolean[N+1];
            arr[i] = bfs(i);
            max = Math.max(max, arr[i]);
        }

        // 최대값에 해당하는 번호 저장
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            if (max == arr[i]) {
                sb.append(i + " ");
            }
        }

        System.out.println(sb);
    }

    static int bfs(int n) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        visited[n] = true;
        int cnt = 1;

        while (!queue.isEmpty()) {
            Integer p = queue.poll();

            for (int i : graph.get(p)) {
                if (!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                    cnt++;
                }
            }
        }
        return cnt;
    }
}