[BOJ] 1325 효율적인 해킹

효율적인 해킹

풀이

• 시간초과 계속 남ㅠ
• A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다. 라는 설명 때문에 node[B].add(A) 로 구현하고, count[B]++ 로 했는데, 이렇게 하면 시간초과.
• node[A].add(B) 로 구현하고, dfs 또는 bfs를 돌면서 count[B]++ 로 count를 증가시키면, B가 해킹할 수 있는 컴퓨터의 수가 늘어나는 것으로 표현할 수 있음.
• dfs로 하면 왜 시간초과지..? 걍 bfs로 하겠음^^..

코드

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

public class BOJ1325 {
    static ArrayList<Integer>[] node;
    static boolean[] visited;
    static int maxV = 0;
    static ArrayList<Integer> answer = new ArrayList<>();
    static int cnt[];
    public static void main(String[] args) throws Exception{
       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        node = new ArrayList[N];
        cnt = new int[N];
        
        for (int i = 0; i < N; i++)
            node[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken()) - 1;
            int B = Integer.parseInt(st.nextToken()) - 1;
            node[A].add(B);
        }
        
        for (int i = 0; i < N; i++) {
            visited = new boolean[N];
            bfs(i);
            //visited[i] = true;
            //dfs(i);
        }
        
        for (int i = 0; i < N; i++) {
            if (cnt[i] > maxV) {
                maxV = cnt[i];
                answer.clear();
                answer.add(i + 1);
            } else if (cnt[i] == maxV) {
                answer.add(i + 1);
            }
        }

        for (int ans : answer) {
            sb.append(ans).append(" ");
        }
        System.out.println(sb);
    }


    private static void bfs(int i) {
        visited[i] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i);
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            for (int next : node[tmp]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                    cnt[next]++;
                }
            }
        }
    }
}