백준_1325 효율적인 해킹 (BFS)

 

문제 자체는 단순해 보였으나 시간복잡도에 매우 민감한 문제였음

 

교재나 인터넷 상의 다른 코드들과 거의 같은 코드임에도 불구하고 시간초과 발생

사소한 부분이라도 줄이려고 여러번 시도했고 결국엔 통과

 

해당 코드도 어쩔때는 통과하고 어쩔때는 시간초과에 걸린다..ㅎ

 

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

public class BJ_1325_효율적인해킹 {

    static ArrayList<Integer>[] arr;
    static boolean[] visited;
    static int[] resultArr;
    static int n;

    public static void main(String[] args) throws IOException {

        int i, a, b, m;
        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 ArrayList[n+1];
        resultArr = new int[n+1];

        for (i=1; i<n+1; i++) {
            arr[i] = new ArrayList<>();
        }

        for (i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            arr[a].add(b);
        }

        Queue<Integer> queue;
        for (i=1; i<n+1; i++) { // bfs를 따로 뽑지 않고 안에서 구현해야 시간이 조금이라도 줄음
            queue = new LinkedList();
            visited = new boolean[n+1];
            visited[i] = true;
            queue.add(i);

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

                for (int nextNode : arr[nowNode]) {
                    if (!visited[nextNode]) {
                        visited[nextNode] = true;
                        resultArr[nextNode]++;
                        queue.add(nextNode);
                    }
                }
            }
        }

        int max = Integer.MIN_VALUE;
        for (i=1; i<n+1; i++) {
            max = Math.max(max, resultArr[i]);
        }

        StringBuilder sb = new StringBuilder();
        for (i=1; i<n+1; i++) {
            if (resultArr[i] == max) {
                sb.append(i).append(' ');
            }
        }

        System.out.println(sb);
    }


}

 

여러번 제출해본 결과

bfs를 for문 안에 직접 구현하고 (+ Queue 변수 선언을 공통으로),
초기 입력받는 n을 static 변수로 뽑아야지만 시간제한을 아슬아슬하게 통과

 

맞았습니다! 두 개 같은 코드임에도 시간차이 발생

1325번: 효율적인 해킹