[1325번] 효율적인 해킹 ( bfs=queue, 방문노드와 신뢰 계산하는 노드, 시간 초과 )

✅ visited 배열 boolean, answer 배열 int

모든 bfs에 대해서 실행하므로 visited배열을 bfs선언할 때 앞에 선언해주어야 함!

for (int i = 1; i <= N; i++) {
			visited = new boolean[N + 1]; //방문 배열 bfs탐방마다 초기화!!!
			bfs(i);
		}

✅ 시간초과

왜 나는 거지!??
찾아보니,,
이 문제는 할 때마다 시간 초과가 나올 수도 있고 아닐 수도 있다고 한다.
이 경우는 시간 복잡도가 코드 제한시간에 걸쳐서 제출했을 때, 되는 경우도 있고, 안 되는 경우도 있어서라고 한다.

✅ 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static ArrayList<Integer>[] A;
	static boolean[] visited;
	static int[] answer;
	static int N, M;

	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;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		A = new ArrayList[N + 1];
		answer = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			A[i] = new ArrayList<>();
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			A[s].add(e);
		}

		for (int i = 1; i <= N; i++) {
			visited = new boolean[N + 1]; //방문 배열 bfs탐방마다 초기화!!!
			bfs(i);
		}

		int max = 0;
		for (int i = 1; i <= N; i++) {
			max = Math.max(max, answer[i]);
		}

		for (int i = 1; i <= N; i++) {
			if (max == answer[i]) {
				bw.write(i + " ");
			}
		}

		br.close();
		bw.flush();
		bw.close();

	}

	private static void bfs(int node) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(node);
		visited[node] = true;

		while (!queue.isEmpty()) {
			int now = queue.poll();
			for (int n : A[now]) {
				if (!visited[n]) {
					visited[n] = true;
					answer[n]++;
					queue.add(n);
				}
			}
		}
	}

}