#백준_1325 효율적인 해킹 - Java 자바

# 유형 : 탐색, 그래프, BFS, DFS

# 너무 BFS로만 해결하는 것 같아서 DFS로 접근해보았다... 근데 아무리 풀어도 시간초과 발생. 다른 블로그 글 참고하면서 보는데 다 같은 로직인데 게시글을 올려놨길래 잘 못 짠거같아서 계속 수정해보았으나 시간초과. 다른 분들 코드 복붙을 했더니.. 시간초과.. 심지어 같은 로직으로 C++ 코드로 제출했더니 통과..

결국은 BFS로 풀었다. 자바 DFS로 시간초과 없이 풀으신 분은 알려주실 수 있다면 감사하겠습니다.

 

 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p1325 {
    static int N,M;
    static boolean visit[];
    static int arr[];
    static ArrayList<Integer> arrList[]; 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arrList = new ArrayList[N+1];
        arr = new int[N+1];
        
        for(int i=1; i<=N; i++)
            arrList[i] = new ArrayList<>();
        
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            arrList[u].add(v);
        }
        
        for(int i=1; i<=N; i++) {
            visit = new boolean[N+1];
            bfs(i);
        }
        
        int max = 0;
        
        for(int i=1; i<=N; i++) {
            max = Math.max(max, arr[i]);
        }
        StringBuffer sb = new StringBuffer();
        for(int i=1; i<=N; i++) {
            if(arr[i] == max)
                sb.append(i+" ");
        }
        System.out.println(sb.toString());
    }
    public static void bfs(int index) {
        
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(index);
        visit[index] = true;
        
        while(!queue.isEmpty()) {
            int val = queue.poll();
            for(int i=0; i<arrList[val].size(); i++) {
                int v = arrList[val].get(i);
                if(!visit[v]){
                    visit[v] = true;
                    arr[v]++;
                    queue.add(v);
                }
            }
        }
    }
    public static void dfs(int index) {
        // TODO Auto-generated method stub
        visit[index] = true;
        
        for(int i=0; i<arrList[index].size(); i++) {
            if(!visit[arrList[index].get(i)]) {
                arr[arrList[index].get(i)]++;
                dfs(arrList[index].get(i));
            }
        }
    }
}