[백준] 31791 - 바이러스 공격 (Java)

문제

무시무시한 테러 단체 '타도 유해조류 산지니'가 부산대학교에 바이러스를 살포하겠다고 예고했다. 
$N$행 
$M$열의 격자로 이루어진 부산대학교 위에는 
$B$개의 건물이 구역 안에 겹치지 않고 있으며, 부산대학교의 철통같은 보안 덕에 테러 단체가 건물에는 바이러스를 살포하지 못한다.

테러에 사용될 바이러스는 아래의 세 가지 특징이 있다.

1. 건물의 내부와 외부에 존재하는 모든 바이러스는 살포 시점으로부터 $T_{G}$시간 뒤 전파를 멈춰 바이러스가 더 이상 주변으로 퍼지지 않는다.
2. 바이러스로부터 안전하지 않은 구역과 상하좌우로 인접한 구역은 $1$시간 뒤 바이러스의 전파가 완료되며, 전파가 완료되기 전까지 인접한 구역은 전파되지 않은 구역으로 간주한다. 두 구역이 서로 변을 공유할 때 인접한다고 한다.
3. 건물에 바이러스가 전파된 시점으로부터 $T_{B}$시간 동안은 건물 내부에 바이러스가 퍼진다. 이 기간 동안 건물 내부는 바이러스가 전파되지 않은 층으로 대피할 수 있어 안전하다. 바이러스가 전파된 지 $T_{B}$시간이 지난 뒤 모든 층에 바이러스가 전파되어 건물이 더이상 안전하지 않게 되면 마찬가지로 상하좌우로 인접한 구역에 $1$시간 뒤 바이러스가 전파된다.

 

하나의 구역은 격자의 한 칸을 의미하며, 바이러스가 전파되지 않은 구역과 바이러스가 전파된 시점으로부터 
$T_{B}$시간이 지나지 않은 건물을 안전한 구역, 그 외 모든 구역을 안전하지 않은 구역으로 분류한다.

산지니는 테러에 부산대학교 학우들이 휩쓸리지 않도록 안전한 곳으로 대피시키고 싶어 한다. 바이러스를 피해 대피할 수 있는 구역을 구해주자.

---

입력

 

출력

 

---

해결 방법

문제를 해결하지는 못했지만 풀어나간 과정입니다. 

 

• 공통 사항 
  • 빈 곳은 0
  • 바이러스는 -1
  • 건물은 건물에서 전파가 지연되는 시간 (T_B)로 배열에 기록
  • -1이 되면 바이러스를 퍼뜨릴 수 있는 상태임.

 

## 첫번째 시도

• 매 시간마다 bfs로 바이러스 위치를 찾고, 바이러스 위치에서 전파 시도

-> 시간초과

O(N*M*T)는 오래 걸림

 

## 두 번째 시도

• 한번 퍼진 지역에서는 바이러스 전파를 할 필요 없음 (이미 사방에 퍼뜨렸기 때문에 더 이상 전파 불가)
• 시작할 때 바이러스의 위치를 queue로 받고, 새로 전파된 지역을 다시 queue에 넣어주는 방식
• 바이러스 위치였다면 전파 시도, 건물 위치였다면 자기 위치의 값을 -1하고 다시 queue에 넣어주기

-> 시간 초과

• 만약 바이러스가 건물에 있고, 건물에서 바이러스가 퍼지기까지의 시간 값이 높다면?
  -> 계속해서 건물 시간 -1, queue에 다시 넣기 작업을 반복해 줘야함.

 

## 세 번째 시도

• 만약에 바이러스가 건물에만 있다면 타임 점프 시도
  • 바이러스가 퍼지기 시작하기까지 가장 짧은 시간이 남은 건물의 시간을 기준으로 (A)
  • A가 전체 남은 시간보다 크다면 -> 종료
  • A가 전체 남은 시간 보단 적다면
    • 건물들에 대해 A만큼씩 빼주고, 전체 남은 시간도 A만큼 빼줌

-> 시간 초과

• 여전히 많은 시간이 걸린다.

 

어떻게 풀어야 했을까??

• 다익스트라 적용 로직
  1. 우선순위 큐 사용 : [시간, y, x] 형태의 데이터를 담고, 시간이 짧은 순으로 정렬
  2. time[n][m] 배열 : 각 칸에 바이러스가 전파되는 최소 시간을 저장하며, 초기 값은 충분히 큰 값으로 설정
  3. 초기 상태 : 처음부터 바이러스가 있는 위치들을 큐에 넣고 time[y][x]= 0으로 설정
  4. 탐색
     1. 큐에서 가장 시간이 적게 걸리는 칸 꺼내기
     2. 상하좌우를 살피며 다음칸으로 이동할때..
        1. 빈칸이면 nextTime = currentTime + 1
        2. 건물이면 nextTime = currentTime + 1 + b
     3. nextTime이 time[ny][nx] 보다 작고, 전체 시간이하라면 값을 갱신하고 큐에 넣기
• 불필요한 반복 제거 - 바이러스가 전파될 가능성 있는 경로만 우선순위 큐를 통해 탐색
• 시간 복잡도 : O(ElogV)수준으로 줄어듬.
• 정확성 : 건물을 만났을 때, 전파 시작을 기다리지 않고 미리 계산하여 큐에 넣으므로 매 시간 업데이트 필요 없

import java.util.*;
import java.io.*;

public class Main {
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int G = Integer.parseInt(st.nextToken()); // 총 시간
        int B = Integer.parseInt(st.nextToken()); // 내구도
        int X = Integer.parseInt(st.nextToken()); // (문제의 추가 변수 X)
        int numBuilding = Integer.parseInt(st.nextToken());

        int[][] boardType = new int[n][m]; // 0: 빈칸, 1: 건물, 2: 초기 바이러스
        int[][] minTime = new int[n][m];
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            Arrays.fill(minTime[i], Integer.MAX_VALUE);
            for (int j = 0; j < m; j++) {
                char c = line.charAt(j);
                if (c == '*') { // 초기 바이러스
                    boardType[i][j] = 2;
                    minTime[i][j] = 0;
                    pq.add(new int[]{0, i, j});
                } else if (c == '#') {
                    boardType[i][j] = 1;
                } else {
                    boardType[i][j] = 0;
                }
            }
        }

        // 다익스트라 수행
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int t = curr[0];
            int y = curr[1];
            int x = curr[2];

            if (t > minTime[y][x]) continue;

            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];

                if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                    // 다음 칸이 바이러스가 되는 데 걸리는 비용 계산
                    int cost = (boardType[ny][nx] == 1) ? B + 1 : 1;
                    int nextT = t + cost;

                    if (nextT <= G && nextT < minTime[ny][nx]) {
                        minTime[ny][nx] = nextT;
                        pq.add(new int[]{nextT, ny, nx});
                    }
                }
            }
        }

        // 결과 출력 (G시간 이후에도 바이러스가 되지 않은 칸)
        StringBuilder sb = new StringBuilder();
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 초기 바이러스도 아니고, 걸린 시간이 G를 초과하면 생존
                if (boardType[i][j] != 2 && minTime[i][j] > G) {
                    sb.append((i + 1)).append(" ").append((j + 1)).append("\n");
                    count++;
                }
            }
        }

        if (count == 0) System.out.println(-1);
        else System.out.print(sb);
    }
}