[백준 JAVA] 31809 : malware 박멸하기

[백준 31809] malware 박멸하기 : https://www.acmicpc.net/problem/31809

---

문제 조건

시간을 신경쓸 필요가 없어보인다. 하루에 박멸 이후 감염이 차례로 진행된다고 이해할 수 있다. 
따라서 자신에게 진입 간선이 존재한다면 박멸 이후 감염이 이뤄지므로 아무런 일도 일어나지 않는다.

 

위에서 말했던 것에 대한 예시를 확인할 수 있다.
진입 간선이 존재한다면, 박멸 이후 감염된다.

주기(P)와 C의 크기가 다른 것이 처음 문제를 읽을 때 조금 헷갈렸다. 

 

---

문제 해결 방법

 

문제의 핵심은 현재 박멸이 진행되는 컴퓨터(노드)에 진입하는 간선(즉, 외부에서 감염될 가능성)이 있다면, 해당 컴퓨터는 다시 감염될 수 있어 즉시 처리할 수 없다는 점이다.

따라서 진입 간선이 없는 노드를 우선적으로 찾아야 한다.

 

이를 다른 관점에서 해석하면, 모든 노드의 진입 간선이 1 이상이라면, 어떠한 노드도 박멸할 수 없으므로 단번의 계산을 통해 즉시 답을 도출해서 최적화할 수 있다.

 

따라서 진입 간선이 없는 노드를 기준으로만 박멸을 수행하고, 이를 기반으로 전체적인 연쇄 반응을 추적하는 것이 문제 해결의 핵심 전략이 됩니다.

 

---

 

코드

 

위 방법을 활용해서 문제를 2가지 방법으로 풀어봤다. 기준은 우선순위큐의 사용유무다.

 

우선순위 큐를 사용하지 않음

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BJ31809 {

    static int MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(bufferedReader.readLine());
        StringBuilder results = new StringBuilder();

        while (tc-- > 0) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int N = Integer.parseInt(stringTokenizer.nextToken());
            int M = Integer.parseInt(stringTokenizer.nextToken());
            int P = Integer.parseInt(stringTokenizer.nextToken());
            int K = Integer.parseInt(stringTokenizer.nextToken());

            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int[] C = new int[N+1];
            for (int i = 1; i <= N; i++) {
                C[i] = Integer.parseInt(stringTokenizer.nextToken());
            }

            // P(주기)의 관점에서 바라본 박멸 순서
            int[] schedule = new int[P + 1];
            for (int i = 1; i <= N; i++) {
                schedule[C[i]] = i;
            }
            schedule[0] = schedule[P];

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

            int[] indegree = new int[N + 1];

            while (M-- > 0) {
                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                int X = Integer.parseInt(stringTokenizer.nextToken());
                int Y = Integer.parseInt(stringTokenizer.nextToken());

                graph.get(X).add(Y);
                indegree[Y]++;
            }

            // 최소 진입 간선 확인
            int minIndegree = Integer.MAX_VALUE;
            for (int curr : indegree) {
                minIndegree = Math.min(minIndegree, curr);
            }
            if (minIndegree > 0) {
                results.append(((long) N * K) % MOD).append("\n");
                continue;
            }

            int currMalware = N;
            long result = 0;
            int cycleDetector = 0;

            boolean[] finished = new boolean[N + 1];
            int day = 0;
            while (++day <= K) {
                int targetComputer = schedule[day % P];

                if (!finished[targetComputer] && targetComputer != 0 && indegree[targetComputer] == 0) {
                    finished[targetComputer] = true;
                    currMalware--;
                    cycleDetector = 0;

                    for (int to : graph.get(targetComputer)) {
                        indegree[to]--;
                    }
                } else {
                    cycleDetector++;
                }

                // P(주기)동안 멀웨어가 줄어들지 않았다면 단번에 계산 가능
                if (cycleDetector == P) {
                    result = result + ((long) currMalware * (K - day + 1) % MOD) % MOD;
                    break;
                }

                result = (result + currMalware % MOD) % MOD;
            }

            results.append(result % MOD).append("\n");
        }

        System.out.println(results.toString().trim());
    }
}

 

 

---

 

우선순위 큐를 사용함

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ31809_pq {

    private static class Computer {
        int idx;
        int day;

        public Computer(int idx, int day) {
            this.idx = idx;
            this.day = day;
        }
    }

    static int MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(bufferedReader.readLine());
        StringBuilder results = new StringBuilder();

        while (tc-- > 0) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int N = Integer.parseInt(stringTokenizer.nextToken());
            int M = Integer.parseInt(stringTokenizer.nextToken());
            int P = Integer.parseInt(stringTokenizer.nextToken());
            int K = Integer.parseInt(stringTokenizer.nextToken());

            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int[] C = new int[N + 1];
            for (int i = 1; i <= N; i++) {
                C[i] = Integer.parseInt(stringTokenizer.nextToken());
            }

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

            int[] indegree = new int[N + 1];

            while (M-- > 0) {
                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                int X = Integer.parseInt(stringTokenizer.nextToken());
                int Y = Integer.parseInt(stringTokenizer.nextToken());

                graph.get(X).add(Y);
                indegree[Y]++;
            }

            // 진입 간선은 PQ의 조건에 포함되지 않는다: 진입 간선이 존재한다면 PQ에 포함될 수 없다
            PriorityQueue<Computer> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.day));
            for (int i = 1; i <= N; i++) {
                if (indegree[i] == 0) {
                    pq.offer(new Computer(i, C[i]));
                }
            }

            int currMalware = N;
            long result = 0;
            int currDay = 0;
            boolean[] finished = new boolean[N + 1];

            while (++currDay <= K) {
                // 처리할 수 있는 컴퓨터가 없다면 계산 후 종료
                if (pq.isEmpty()) {
                    result = (result + fastForward(K - currDay + 1, currMalware)) % MOD;
                    break;
                }

                Computer currComputer = pq.poll();
                if (finished[currComputer.idx]) {
                    continue;
                }
                finished[currComputer.idx] = true;
                // 기한 내에 처리할 수 있는 컴퓨터가 없다면 계산 후 종료
                if (currComputer.day > K) {
                    result = (result + fastForward(K - currDay + 1, currMalware)) % MOD;
                    break;
                }

                // 현재 날짜에 처리할 수 있는 컴퓨터가 없다면 처리할 수 있는 날까지 건너뛰기
                if (currComputer.day > currDay) {
                    result = (result + fastForward(currComputer.day - currDay, currMalware)) % MOD;
                    currDay = currComputer.day;
                }

                currMalware--;

                // 자신이 박멸되므로 박멸될 수 있는 요소를 큐에 추가
                for (int adj : graph.get(currComputer.idx)) {
                    indegree[adj]--;
                    if (indegree[adj] == 0 && !finished[adj]) {
                        int nextScheduledDay = calcNextScheduledDay(adj, currDay, C, currComputer, P);
                        pq.offer(new Computer(adj, nextScheduledDay));
                    }
                }

                result = (result + currMalware) % MOD;
            }

            results.append(result).append("\n");
        }

        System.out.println(results.toString().trim());
    }

    // 최적화: fast-forward를 수행하여 i일 동안 변화가 없는 박멸 개수를 한 번에 계산
    private static long fastForward(int i, int currMalware) {
        return (((long) currMalware * i) % MOD) % MOD;
    }

    // C를 고려해서 다음으로 박멸될 컴퓨터의 day를 계산
    private static int calcNextScheduledDay(int adj, int currDay, int[] C, Computer currComputer, int P) {
        int nextScheduledDay = currDay + C[adj] - C[currComputer.idx];
        if (C[currComputer.idx] > C[adj]) {
            nextScheduledDay += P;
        }
        return nextScheduledDay;
    }
}

 

---

마무리

 

우선순위 큐를 활용한 방식이 결과적으로 약 10% 정도 더 빠른 성능을 보였다.

엣지 케이스가 많았다면 성능 차이가 눈에 띄게 나타났겠지만, 결국 중요한 점은 두 코드에서 모두 사용한 반복되는 연산을 최소화하는 최적화 전략(fast-forward)이다.

 

최근 다시 알고리즘 문제를 풀면서, 객체 지향적인 방식으로 접근하는 것이 맞는지, 혹은 알고리즘 자체에 집중하는 것이 맞는지에 대한 고민이 든다. 우선 구른다