BOJ_1325_에어컨

말도 안 되게 시간 초과에 까다로워서 좋지 않은 문제지만 ArrayDeque와 LinkedList에 대해서 더 공부할 수 있었다

너비 우선 탐색(BFS) 나 DFS로 풀 수 있는 것 같은데 이 문제에서는 BFS 만 시간 초과가 안 났다

처음에 ArrayDeque로 Queue를 구현했는데 시간 초과가 났고, 동일한 코드를 LinkedList로 구현체를 변경하니까 시간 안에 들어왔다

기본적으로 ArrayDeque는 연속된 메모리를 사용해 캐시 효율성이 LinkedList보다 높다. LinkedList는 메모리상에서 요소들이 흩어져 있어 캐시 미스가 더 자주 발생한다. 또한 LinkedList는 이전/다음 노드 참조를 저장해야 해서 요소당 메모리 사용량이 더 크다.

그래서 대부분의 상황에서는 ArrayDeque가 더 효율적이며 BFS에서도 마찬가지라고 한다. 왜냐면 BFS는 1) 보통 한 번에 모든 노드를 방문하지 않으므로 급격한 큐 크기 변화가 적으며 2) 크기 변화로 인한 재할당이 많이 발생하지 않기 때문이다.

하지만 이 문제의 경우 테스트 케이스가 LinkedList에 유리하게 있던 것 같다.

BFS에서 LinkedList가 더 효율적일 수 있는 경우

• 그래프의 구조가 매우 불규칙하여 큐의 크기가 급격하게 변할 때
• 메모리 할당/해제가 빈번하게 일어나는 환경에서
• 큐의 최대 크기가 매우 클 때 (ArrayDeque의 재할당 비용이 커질 수 있음)

package BJO;

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

public class BJO_1325_효율적인해킹 {
    static ArrayList<Integer>[] graph;
    static int N, M;
    static boolean[] visited;
    static int[] count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N + 1];
        count = new int[N + 1];

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

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

        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];

            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            visited[i] = true;

            while (!queue.isEmpty()) {
                int current = queue.poll();
                for (int next : graph[current]) {
                    if (!visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                        count[next]++;
                    }
                }
            }
        }

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

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            if (count[i] == max) {
                sb.append(i).append(" ");
            }
        }

        System.out.println(sb);
    }
}