[백준/java] 1325. 효율적인 해킹

문제 보기

문제

컴퓨터 신뢰관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력

• 입력 : 컴퓨터 수 N (<= 10^4) , 관계 수 M ( <= 10^5), M개의 관계
• 출력 : 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호 오름차순 출력

문제 풀이 1 - DFS

static Map<Integer, List<Integer>> map = new HashMap<>(); // key : 컴퓨터 번호 n, values : n 컴퓨터를 신뢰하는 컴퓨터 리스트
    static int[] comcnt; // 해킹 가능한 컴퓨터 수

hashmap 형태로 입력 관계를 저장하고, 해킹 가능한 컴퓨터 수 배열은 추후 dfs 탐색 과정을 거치면서 저장할 것이다.

for(int i = 1;i<=N;i++){
            boolean[] visited = new boolean[N + 1];
            int count = dfs(i, visited);
            comcnt[i] = count;
            max = Math.max(max, count);
        }

각 컴퓨터(1~N)를 시작점으로 dfs를 수행하여 총 N번의 dfs 과정을 돈다.

private static int dfs(int node, boolean[] visited) {
        visited[node] = true;
        int cnt = 1;
        if (map.containsKey(node)) {
            for (int next : map.get(node)) {
                if (!visited[next]) {
                    cnt += dfs(next, visited);
                }
            }
        }
        return cnt;
    }

dfs함수는 O(N+M)이고,
총 시간복잡도는 O(N(N+M))이다.
이를 계산하면, 1.1 10^9로 5초 제한 시간 내에 코드가 성공적으로 돌아간다.

🧐 메모이제이션 시도 -> 실패

컴퓨터 하나에 대한 dfs 과정이 중복되어 메모이제이션을 넣어 시간복잡도를 줄이려 하였다.
근데 visited와 충돌해서 정답 코드가 나오지 않았다.

문제 풀이 2 - BFS 풀이 -> 실패 ??

bfs 풀이 방식으로 풀었다.

private static int bfs(int node, int N) {
       boolean[] visited = new boolean[N + 1];
       Queue<Integer> queue = new LinkedList<>();
       visited[node] = true;
       queue.add(node);

       int cnt = 1;

       while (!queue.isEmpty()){
           int cur = queue.poll();
           for(int next : graph[cur]){
               if(!visited[next]){
                   queue.offer(next);
                   cnt++;
                   visited[next] = true;
               }
           }
       }ㅂ
       return cnt;
   }

재귀 호출 오버헤드 부담을 줄이고, visited 처리가 명확한 bfs 방식이 이번 풀이에 더 용이한 거 같다고 생각했는데 시간초과가 떴다,..?