[알고리즘] 백준 - 효율적인 해킹

백준 - 효율적인 해킹

시간 초과한 내 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;


public class Main {
    static int N, M;
    static List<List<Integer>> graph = new ArrayList<>();
    static int[] arr;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        M = Integer.parseInt(inputs[1]);
        arr = new int[N + 1];

        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            inputs = br.readLine().split(" ");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);

            graph.get(a).add(b);
        }

        for (int i = 0; i < N + 1; i++) {
            visited = new boolean[N+1];
            dfs(i);
        }
        int maxVal = Arrays.stream(arr).max().getAsInt();
        for (int i = 1; i < N + 1; i++) {
            if (arr[i] == maxVal) {
                System.out.print(i + " ");
            }
        }
    }

    private static void dfs(int curPos) {
        visited[curPos] = true;
        arr[curPos]++;
        for (int adjNode : graph.get(curPos)) {
            if (!visited[adjNode]) {
                dfs(adjNode);
            }
        }
    }
}

주어진 입력의 방향을 바꿔서 그래프를 만들었다. 그래서 1이 몇개의 컴퓨터를 지나냐 이런식으로 했고, 그 정답은 HashMap에 저장했다.

통과한 내풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;


public class Main {
    static int N, M;
    static List<List<Integer>> graph = new ArrayList<>();
    static int[] arr;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        M = Integer.parseInt(inputs[1]);
        arr = new int[N + 1];

        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            inputs = br.readLine().split(" ");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);

            graph.get(a).add(b);
        }

        for (int i = 0; i < N + 1; i++) {
            visited = new boolean[N+1];
            dfs(i);
        }
        int maxVal = Arrays.stream(arr).max().getAsInt();
        for (int i = 1; i < N + 1; i++) {
            if (arr[i] == maxVal) {
                System.out.print(i + " ");
            }
        }
    }

    private static void dfs(int curPos) {
        visited[curPos] = true;
        arr[curPos]++;
        for (int adjNode : graph.get(curPos)) {
            if (!visited[adjNode]) {
                dfs(adjNode);
            }
        }
    }
}

크게 바뀐건 없다. 방향을 원래 입력대로하고, 지나갈때마다 arr[node]++해줬다. 하지만 이 코드도 통과했지만 시간이 매우 많이 나왔고, bufferdwriter를 쓰니 또 통과하지 못했다. 이유는 생각해봐야겠다.