BOJ - 효율적인 해킹 1325번 (JAVA)

❓ 문제 - 백준 효율적인 해킹 1325번 - JAVA 풀이법

 

출처 

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

1325번: 효율적인 해킹

 

 

📝 문제해결법

1. 이 문제는 BFS 알고리즘을 사용해서 풀었다.

• 일단 노드의 갯수가 최대 10,000 이고 간선은 100,000 정도이므로 시간복잡도를 고려해서 시간초과 안나도록 해야한다. --> 특히 자바 ^^...
• 처음 A가 B를 신뢰하면 인접리스트를 통해 A 인덱스에 B의 값을 넣어준다.
• 그리고 cnt라는 배열을 만들어줘서 신뢰관계를 통해 얼마나 다른 컴퓨터를 해킹할 수 있을지 세어준다.
• 1~N개의 컴퓨터를 기준으로 BFS를 돌면서 얼마나 다른 컴퓨터를 해킹할 수 있을지 값을 변경해준다.
• BFS 함수 안에서는 방문처리를 위해 visited 배열을 활용했고, 큐를 통해서 해당 노드와 다른 노드가 연결(B를 통해 A를 방문 -> A가 B를 신뢰)된 것이므로 다른 노드에 해당하는 해킹 가능한 카운트를 +1 증가해준다.
• 마지막에 cnt 배열을 돌면서 가장 크게 해킹 가능한 노드를 찾고, 만약 최대값이 여러 존재한 경우도 존재하기 때문에 ans 리스트에 값을 넣어주고 그대로 출력한다.
• cnt에서 해킹 카운트를 접근할 때 for문으로 i 인덱스부터 차례대로 처리하므로 오름차순 정렬을 할 필요가 없다.

2. 시간 초과 

• 똑같은 구현내용을 파이썬으로 하면 시간초과가 나는데 왜 자바는 안될까 ?에 대한 많은 고민을 했다.
• 일단 인접리스트를 만들 때 LinkedList보다 ArrayList가 빠르기 때문에 리스트를 활용할 땐 다 ArrayList로 만들어서 활용한다.
• 그리고 A가 B를 신뢰하는 경우 인접리스트를 형성할 때 B인덱스에 A를 넣어 BFS 탐색을 하도록 했는데 그러면 1 ~ N 컴퓨터에서 BFS를 돌 때 이미 연결된 관계를 계속 돌 수 있다.
• 예제1을 살피면 1번 컴퓨터를 BFS를 돌면 3, 4, 5 컴퓨터 방문, 2번 컴퓨터를 돌면 3, 4, 5 컴퓨터 방문, 3번 컴퓨터를 돌면 4, 5번 컴퓨터 방문으로 처리한다.
• 하지만 위의 시간초과를 고려해서 위의 방식으로 코드를 구현하면 1번 X, 2번 X, 3번 1, 2번 컴퓨터 방문, 4번 3-1, 3-2 번 방문, 5번 3-1, 3-2 방문으로 처리한다. 훨씬 방문하는 횟수를 줄일 수 있기 때문이다. => 여기서 많이 시간 절약 한 듯 ..

3. 문제를 풀면서 느낀점

• 자바는 자료구조를 활용할 때 시간복잡도를 생각하고 써야겠다..
• 아무리 쉽고 익숙한 풀이로 느껴져도 항상 데이터 범위가 넓을 땐 시간 복잡도를 고려하는 습관을 가지자 ~~~~~

 

 

💻 소스코드

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

public class Main_1325 {
    public static List<Integer>[] list;
    public static int[] cnt;
    public static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        list = new ArrayList[n+1];

        for(int i=0;i<=n;i++){
            list[i] = new ArrayList<Integer>();
        }
        for(int i=0;i<m;i++){
            String[] data = br.readLine().split(" ");
            int a = Integer.parseInt(data[0]);
            int b = Integer.parseInt(data[1]);
            list[a].add(b);

        }

        cnt = new int[n+1];

        for(int i=1;i<=n;i++){
            bfs(i);
        }

        ArrayList<Integer> ans = new ArrayList<>();
        int max_value = 0;
        for(int i=1;i<=n;i++){
            if(cnt[i] > max_value){
                max_value = cnt[i];
                ans.clear();
                ans.add(i);
            } else if (cnt[i] == max_value){
                ans.add(i);
            }
        }

        for(int a:ans){
            System.out.print(a+" ");
        }


    }

    public static void bfs(int start){
        boolean[] visited = new boolean[n+1];
        Queue<Integer> q = new LinkedList<>();
        visited[start] = true;
        q.offer(start);

        while (!q.isEmpty()) {
            int x = q.poll();
            for (int num : list[x]) {
                if (!visited[num]) {
                    cnt[num]++;
                    visited[num] = true;
                    q.offer(num);
                }
            }
        }


    }

}