[백준 1325] 효율적인 해킹 - JAVA

BOJ Link

https://www.acmicpc.net/problem/1325

 

 

 

 

 

 

풀이 과정

일반적인 그래프 탐색이나, 시간초과 조건이 조금 빡세서 정답률이 18%였다.

인접 배열대신 리스트로 구현해야했고, 단방향 그래프의 간선 순서가 반대로 주어짐에 주의해야 했다.

 

int n = next.get(j);
if (!vst[n]) {
    vst[n] = true;
    q.offer(n);
    cnt++;
}

 

한 번 시간초과를 받은 이유에 list.get(j)를 3번 적은 동작이 있었다. 자바가 내부적으로 캐싱을 해주지 않을까 해서 썼는데, 안해준다고 한다. 이는 단순히 변수로 저장하고 써서 통과했다.

 

 

제출 코드

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<List<Integer>> adj = new ArrayList<>();

        for (int i = 0; i <= N; i++) adj.add(new ArrayList<>());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken());
            int from = Integer.parseInt(st.nextToken());
            adj.get(from).add(to);
        }

        int ans = 0;
        List<Integer> ansList = new ArrayList<>();

        for (int i = 0; i <= N; i++) {
            if (adj.get(i).isEmpty()) continue;

            boolean[] vst = new boolean[N + 1];
            Queue<Integer> q = new ArrayDeque<>();
            vst[i] = true;
            q.offer(i);

            int cnt = 1;

            while (!q.isEmpty()) {
                List<Integer> next = adj.get(q.poll());

                for (int j = 0; j < next.size(); j++) {
                    int n = next.get(j);
                    if (!vst[n]) {
                        vst[n] = true;
                        q.offer(n);
                        cnt++;
                    }
                }
            }

            if (cnt == ans) {
                ansList.add(i);
            } else if (cnt > ans) {
                ans = cnt;
                ansList.clear();
                ansList.add(i);
            }
        }

        StringBuilder sb = new StringBuilder();
        ansList.stream().sorted().forEach(i -> sb.append(i).append(" "));
        System.out.println(sb);
    }
}