효율적인 해킹(1325)

효율적인 해킹(1325)

풀이

• 이번 문제는 메모리 초과떠서 어지러웠다.. 2차원 배열을 Arraylist로 바꾸어서 해결하니까 통과 하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class FastScanner {
    BufferedReader br;
    StringTokenizer st;

    public FastScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }
}

public class Main {
    static int n;   // Computer size
    static int m;   // Edge size
    static ArrayList<Integer> computer[];
    static int countVisit [];
    static boolean visited[];
    static int cnt = 0;
    static Vector<Hacking> pq = new Vector<>();

    public static void main(String args[]) throws IOException {
        FastScanner sc = new FastScanner();

        n = sc.nextInt();
        m = sc.nextInt();

        computer = new ArrayList[n+1];
        countVisit = new int[n+1];

        for(int i=1; i<=n; i++)
            computer[i] = new ArrayList<>();

        for(int i=0; i<m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();

            computer[a].add(b);
        }

        for(int i=1; i<=n; i++){
            cnt = 1;
            bfs(i);
        }

        for(int i=1; i<=n; i++)
            pq.add(new Hacking(i,countVisit[i]));


        Collections.sort(pq, new Comparator<Hacking>() {
            public int compare(Hacking p1, Hacking p2) {
                if(p1.cost > p2.cost) {
                    return -1;
                }
                else if(p1.cost == p2.cost) {
                    return Integer.compare(p1.num, p2.num);
                }
                else {
                    return 1;
                }
            }
        });


        int max = pq.get(0).cost;

        for(int i=0; i<pq.size(); i++){
            if(max != pq.get(i).cost)
                break;
            System.out.print(pq.get(i).num + " ");
        }

    }

    public static void bfs(int start){
        visited = new boolean[n+1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while(!queue.isEmpty()){
            int cur = queue.poll();

            for(var next : computer[cur]){
                if(!visited[next]){
                    visited[next] = true;
                    queue.add(next);
                    countVisit[next]++;
                }
            }
        }
    }
}


class Hacking{
    int num;
    int cost;

    public Hacking(int num, int cost){
        this.num = num;
        this.cost = cost;
    }
}