경쟁적 전염 - 백준 18405 번

18405번: 경쟁적 전염

 

1. 문제

K개의 바이러스 종류가 존재 합니다. N x N 의 실험실이 존재 합니다. 바이러스는 상, 하, 좌, 우로만 전파 될 수 있고, 전파 될 위치의 다른 바이러스가 이미 전파를 하였으면, 전파 할수 없습니다. 그리고 바이러스의 종류 번호가 낮은 번호가 우선순위를 가지고 전파 됩니다. 바이러스가 전파되지 않은 곳은 0이라고 합니다. 이때 N과 K, 그리고 실험실 칸 마다의 어떤 종류의 바이러스가 전파 되었는지 입력으로 주어 진다면, S초 후에 (X, Y) 좌표에는 어떤 종류의 바이러스가 전파 되었는지 출력 하시오.

 

 

2. 접근

1. 상, 하, 좌, 우로 바이러스가 전파 되므로 BFS(너비 우선 탐색)으로 해결 한다.

2. 바이러스의 (x, y) 좌표와 바이러스 종류, 바이러스가 전파된 시간을 담을 수 있는 Node 라는 자료구조를 만듭니다.

3. 바이러스가 전염 될 경우 Queue의 바이러스에 대한 정보를 넣어 주고,

4. Queue에서는 시간 순으로 바이러스의 대한 정보를 꺼냅니다. 시간이 같다면, 바이러스의 종류가 낮은 순으로 Queue에서 바이러스를 꺼냅니다.

5. S초에 도달 하였다면, 그때의 실험실[목표 X][목표 Y] 값을 반환 합니다.

 

 

3. Java 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ18405 {
    // https://www.acmicpc.net/problem/18405
    // 경쟁적 전염
    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 K = Integer.parseInt(st.nextToken());

        int[][] map = new int[N][N];
        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());
            }
        }

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

        System.out.print(new BOJ18405().solution(N, map, S, X, Y));
    }

    public int solution(int n, int[][] map, int s, int x, int y) {
        // 바이러스의 타입 중 가장 작은 타입 부터 전염(PriorQueue 특성)
        Queue<Node> queue = new PriorityQueue<Node>();

        // 이미 감염 되어있는 노드들을 queue 에 넣어줌
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 0) {
                    queue.offer(new Node(i, j, map[i][j], 0));
                }
            }
        }

        return bfs(queue, map, s, x - 1, y - 1, n);
    }

    private int bfs(Queue<Node> queue, int[][] map, int s, int desX, int desY, int n) {
        int[] dx = new int[]{1, -1, 0, 0};
        int[] dy = new int[]{0, 0, 1, -1};

        while(!queue.isEmpty()) {
            Node cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            int virusType = cur.virusType;
            int time = cur.time;
            if (time == s) break;

            // 바이러스 전파
            for (int i = 0; i < 4; i++) {
                int nextX = x + dx[i];
                int nextY = y + dy[i];
                int nextTime = time + 1;

                if (isInBox(nextX, n) && isInBox(nextY, n) && !isVirus(map, nextX, nextY)) {
                    // 바이러스 전염
                    queue.offer(new Node(nextX, nextY, virusType, nextTime));
                    map[nextX][nextY] = virusType;
                }
            }
        }

        return map[desX][desY];
    }

    private boolean isVirus(int[][] map, int nextX, int nextY) {
        return map[nextX][nextY] != 0;
    }

    private boolean isInBox(int x, int n) {
        return x >= 0 && x < n;
    }
}

class Node implements Comparable<Node> {
    int x;
    int y;
    int virusType;
    int time;

    public Node(int x, int y, int virusType, int time) {
        this.x = x;
        this.y = y;
        this.virusType = virusType;
        this.time = time;
    }

    @Override
    public int compareTo(Node other) {
        if (time != other.time) {
            return time - other.time;
        } else {
            return virusType - other.virusType;
        }
    }
}

 

저는 PriorityQueue 를 사용해서 첫째는 시간 순, 둘째는 바이러스의 종류 순 으로 바이러스의 전염을 표현 하였는데, 다른 방법으로는 처음의 전염된 바이러스를 바이러스 종류 순 으로 정렬 하고 나서, PirorityQueue가 아닌 LinkedList 의 넣어 주어 바이러스의 전염을 표현 하는 방법도 있을거 같습니다.