[백준/Java] 1325번 효율적인 해킹

-Code

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

public class BOJ1325 {
    static ArrayList<Integer>[] computerConnect;
    static int[] visited;

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

        int computerCnt = Integer.parseInt(st.nextToken());
        int connectCnt = Integer.parseInt(st.nextToken());
        visited = new int[computerCnt + 1];
        // 연결을 저장할 배열 셋팅
        computerConnect = new ArrayList[computerCnt + 1];
        for (int i = 0; i <= computerCnt; i++) {
            computerConnect[i] = new ArrayList<>();
        }
        // 연결 갯수 만큼 받기
        for (int conn = 0; conn < connectCnt; conn++) {
            st = new StringTokenizer(br.readLine());
            int end = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());

            computerConnect[start].add(end);
        }
        int[] computerHackingCnt = new int[computerCnt + 1];
        int maxCnt = -1;
        for (int start = 1; start <= computerCnt; start++) {
            // 연결된 신뢰 컴퓨터 갯수 (해킹 갯수) 구하기
            int nowHackingCnt = getHackingCnt(start);
            // 최대값 저장
            maxCnt = Math.max(maxCnt, nowHackingCnt);
            // 해킹 컴퓨터 갯수 저장
            computerHackingCnt[start] = nowHackingCnt;
        }
        // 최대 갯수인 경우 출력
        StringBuilder answer = new StringBuilder();
        for (int start = 1; start <= computerCnt; start++) {
            if (computerHackingCnt[start] == maxCnt) {
                answer.append(start).append(" ");
            }
        }
        System.out.println(answer);
    }

    private static int getHackingCnt(int start) {
        // 해킹 갯수 저장 변수
        int answer = 0;
        // 초기 셋팅
        visited[start] = start;
        Deque<Integer> deq = new ArrayDeque<>();
        deq.addLast(start);
        // 탐색
        while (!deq.isEmpty()) {
            int now = deq.pollFirst();
            // 다음 값 확인
            for (int next : computerConnect[now]) {
                // 신뢰하는 컴퓨터고 방문하지 않은 경우 탐색 추가
                if (visited[next] != start) {
                    visited[next] = start;
                    deq.addLast(next);
                    answer++;
                }
            }
        }
        return answer;
    }
}

처음에 ArrayList <ArrayList <>>와 visited를 모든 시작점마다 생성하여했더니 메모리 초과가 생겼습니다. 그래서 int [][]로 computerConnect를 바꿨지만 문제가 해결되지 않았습니다.

그래서 그냥 ArrayList []로 타협을 하고 visited를 계속 생성하는 것이 메모리 처리에 문제가 있는 것과 처음 한 번만 생성하고 검사 컴퓨터 시작점으로 갱신하면서 다시 생성하지 않도록 하라는 힌트를 얻고 해결했습니다.

뭔가 어려운 느낌은 아닌데 메모리나 시간 초과가 몇 번 떠서 힌트를 얻기 위해 찾아본 게 조금 아쉬웠습니다.