[BOJ 18405] 경쟁적 전염

문제 개요

문제: https://www.acmicpc.net/problem/18405

 

연구소에서 바이러스가 퍼지고 있습니다. 바이러스는 번호가 작을수록 우선적으로 전파되며, 매초 상하좌우 인접한 칸으로 퍼집니다.

연구소는 N x N 크기의 격자이며, 한 칸에 하나의 바이러스만 존재할 수 있습니다. 특정 초가 지난 후, (X, Y) 위치에 존재하는 바이러스의 종류를 출력하세요. (없으면 0 출력)

 

예제

3 3
1 0 2
0 0 0
3 0 0
2 3 2

• N = 3, K = 3 (바이러스 종류는 1~3)
• S = 2초 후, X = 3, Y = 2 (즉, map[2][1]에 어떤 바이러스가 있는지)

2초가 지난 후 배열은 다음과 같습니다.

1	1	2
1	3	2
3	3	2

 

접근 방식

1. 각 바이러스의 위치를 Map<Integer, Queue<int[]>> 자료구조에 저장하여 바이러스 번호별로 큐를 관리합니다.

2. S초 동안 반복하며 매 초마다 바이러스 번호가 작은 것부터 BFS를 수행합니다.

3. BFS 탐색을 통해 빈 칸(값이 0인 칸)에 자신을 증식시킵니다.

4. 다음 단계의 BFS를 위해 현재 확산된 위치를 새로운 큐(newQ)에 저장합니다.

5. 1초가 끝나면 virus 맵을 새롭게 갱신하여 다음 초에도 순서를 유지하도록 합니다.

 

구현

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

public class BOJ_18405_1 {
    static int N;
    static int K;
    static StringTokenizer st;
    static int[][] arr;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int S;
    static int X;
    static int Y;
    static Map<Integer, Queue<int[]>> virus = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        for (int i=1; i<=K; i++) {
            virus.put(i, new LinkedList<>());
        }

        arr = new int[N][N];

        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] <= K && arr[i][j] != 0) {
                    virus.get(arr[i][j]).offer(new int[]{i, j});
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken())-1;
        Y = Integer.parseInt(st.nextToken())-1;

        for (int i=0; i<S; i++) {
            bfs();
        }

        System.out.println(arr[X][Y]);


    }

    static void bfs() {

        for (int i=1; i<=K; i++) {
            Queue<int[]> newQ = new LinkedList<>();
            Queue<int[]> curQ = virus.get(i);
            while (!curQ.isEmpty()) {
                int[] cur = curQ.poll();
                int curX = cur[0];
                int curY = cur[1];

                for (int j=0; j<4; j++) {
                    int nx = curX + dx[j];
                    int ny = curY + dy[j];
                    if (nx >= 0 && nx < N && ny >= 0 && ny < N && arr[nx][ny] == 0) {
                        arr[nx][ny] = i;
                        newQ.offer(new int[]{nx, ny});
                    }
                }
            }
            virus.put(i, newQ);
        }

    }
}

 

위에서 구현한 방식은 바이러스 번호별로 개별 큐를 만들어 시뮬레이션을 수행하는 구조입니다. 하지만 이 방식은 다음과 같은 비효율적인 요소가 존재합니다. 바이러스 번호 수(K)만큼 루프를 매번 돌며 각 큐를 개별 처리해야 하므로 초마다 O(K × 큐 탐색) 만큼 반복됩니다.

 

새로운 접근 방식

기존 방식의 문제점을 해결하기 위해, 모든 바이러스를 하나의 큐에 넣고 시간 순서대로 처리하는 구조로 개선했습니다.

• 하나의 큐로 모든 바이러스 전파를 처리 → 코드 단순화
• 시간(time) 필드를 이용해 시뮬레이션 흐름을 명확하게 추적
• 초기에는 virus 번호 순으로 정렬 → 자동으로 우선순위 보장됨

 

구현

public class BOJ_18405_2 {
    static int N, K, S, X, Y;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static class Virus {
        int x, y, type, time;

        public Virus(int x, int y, int type, int time) {
            this.x = x;
            this.y = y;
            this.type = type;
            this.time = time;
        }
    }

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        List<Virus> virusList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] > 0) {
                    virusList.add(new Virus(i, j, map[i][j], 0));
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken()) - 1;
        Y = Integer.parseInt(st.nextToken()) - 1;

        virusList.sort(Comparator.comparingInt(v -> v.type));
        Queue<Virus> queue = new LinkedList<>(virusList);

        while (!queue.isEmpty()) {
            Virus v = queue.poll();
            if (v.time == S) break;

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

                if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] == 0) {
                    map[nx][ny] = v.type;
                    queue.add(new Virus(nx, ny, v.type, v.time + 1));
                }
            }
        }

        System.out.println(map[X][Y]);
    }
}

 

시간 복잡도 & 공간 복잡도

시간 복잡도: O(N^2 + N^2 × 4) → O(N^2)

공간 복잡도: O(N^2)