[알고리즘-PS] 백준 1325번 효율적인 해킹 자바 문제풀이 (시간 초과 해결)

문제

해당 포스팅은 백준의 1325번 효율적인 해킹 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이 문제는 간단한 dfs/bfs 로 해결할 수 있는 문제이다.

 

총 입력이 1만개가 최악의 경우 들어오고 각각의 노드의 dfs 결과를 탐색해야 하니 조금 간당간당하게 시간 복잡도에 걸릴 수 있다.

 

그래서 이 문제는 일반적인 dfs로 해결하면 시간 초과가 날 수 있는 문제이다.

 

해결법

 

이 문제는 재귀 dfs, 스택 dfs 등 여러 방법을 통해서 구현을 해보았지민 결과를 조금 더 빨리 낼 수 있는 bfs 로 해결하였다.

 

해킹할 수 있는 노드의 수를 표현하기 위해서 static 한 int 배열에 노드 번호를 인덱스로 하여 값을 증가시키는 방향으로 가야 해결할 수 있다.

 

정답 코드

public class Main {

    private static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    private static boolean[] visited;
    private static int[] result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nm = br.readLine().split(" ");

        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

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

        for (int i = 0; i < m; i++) {
            String[] fromTo = br.readLine().split(" ");
            int from = Integer.parseInt(fromTo[0]);
            int to = Integer.parseInt(fromTo[1]);

            graph.get(from).add(to);
        }
        result = new int[n + 1];

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

        int max = 0;

        for (int i = 1; i <= n; i++) {
            max = Math.max(max, result[i]);
        }

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

        bw.flush();
        bw.close();
    }

    private static void getMaxPen(int x) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(x);
        visited[x] = true;

        while(!queue.isEmpty()) {
            int front = queue.remove();
            for(int value : graph.get(front)) {
                if(!visited[value]) {
                    visited[value] = true;
                    queue.add(value);
                    result[value]++;
                }
            }
        }
    }
}

---

 

문제 회고

출력을 최적화 하기 위해서 static 한 변수를 쓴다는 차이에 문제의 ac가 달라졌다는 사실에 조금 신기했고, 다음에도 이런 문제가 나오면 충분히 써볼만 한 문제 해결 방법이었다.

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.