17.경쟁적 전염

📍 문제 설명

💡 접근

바이러스 번호와 초 / x, y 좌표를 필드로 하는 Virus 클래스를 만들어서 리스트에 넣어주고

큐를 이용해서 바이러스 번호가 낮은 것부터 상하좌우로 바이러스 증식을 시키면 되는 문제였다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    public static int[] dx = {-1,1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static int s;
    public static ArrayList<Virus> viruses = new ArrayList<>();
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        //NXN 시험관 크기
        int n = kb.nextInt();
        //바이러스 최대 번호
        int k = kb.nextInt();
        //시험관 정보
        int[][] map = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                map[i][j] = kb.nextInt();
                viruses.add(new Virus(map[i][j], 0, i, j));
            }
        }
        //경과 시간
        int s = kb.nextInt();
        //(x,y) 좌표
        int x = kb.nextInt();
        int y = kb.nextInt();

        //낮은 번호의 바이러스가 먼저 증식하도록 정렬
        Collections.sort(viruses);
        Queue<Virus> q = new LinkedList<>();
        //현재 시험관에 바이러스 정보를 큐에 모두 넣기
        for(int i = 0; i < viruses.size(); i++) {
            q.offer(viruses.get(i));
        }

        while(!q.isEmpty()) {
            //큐에서 꺼내기
            Virus virus = q.poll();

            if(virus.second == s) break;
            //4가지 방향에 대해서 증식
            for(int i = 0; i < 4; i++) {
                int nx = virus.x + dx[i];
                int ny = virus.y + dy[i];
                //증식 가능한 범위이고 바이러스가 없는 곳이라면 증식시키기
                if(nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx][ny] == 0){
                    map[nx][ny] = virus.index;
                    q.offer(new Virus(virus.index, virus.second+1, nx, ny));
                }
            }
        }

        System.out.println(map[x-1][y-1]);

    }

    private static class Virus implements Comparable<Virus> {
        private int index;
        private int second;
        private int x;
        private int y;

        public Virus(int index, int second, int x, int y) {
            this.index = index;
            this.second = second;
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Virus o) {
            return this.index - o.index;
        }
    }
}