[BOJ] 경쟁적 전염(18405)

[백준(BOJ)] 18405_경쟁적 전염 JAVA

문제 : BOJ_18405번 경쟁적 전염

문제 설명

NxN 크기의 시험관에서 바이러스가 매초 상하좌우로 증식한다.

이때 바이러스는 기존의 바이러스가 있는 자리엔 증식할 수 없으며 바이러스마다 증식하는 우선순위 번호가 주어진다.

주어지는 시간(s)에 주어지는 장소(x,y)에 어떤 바이러스가 있는지 출력하는 문제이다.

---

Solution

bfs

bfs를 이용해서 바이러스가 상하좌우로 증식할 때 자료구조에 넣어지는 식으로 풀 수 있다.

다만, 바이러스가 증식하는 우선순위 번호가 있기 때문에 단순한 queue 구조로는 해결할 수 없다.

여러 가지 방법이 있지만 temp list를 선언해서 새로 생성되는 바이러스들을 넣어준 뒤, 한 번의 바이러스 증식이 끝난 뒤에 기존의 list를 temp list로 바꿔주고 정렬하는 식으로 해결했다.

주의할 것은 s초가 되기 전에 bfs가 끝나는 경우가 있으니 이 역시 고려해 줘야 한다.

---

Description

• 바이러스의 좌표와 우선순위는 Node라는 클래스로 담았다.
• list = temp라는 코드로 기존의 리스트를 temp 리스트로 교체한다.
• if(!printAns) bw.write(String.valueOf(map[x][y])+"\n"); : s초가 되기 전에 bfs가 종료되는 경우에 실행되는 코드이다.

---

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Node implements Comparable<Node>{
    private int x;
    private int y;
    private int val;

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getVal() {
        return val;
    }

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

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.val, other.val);
    }
}

public class Main {
    public static int[][] map;
    public static ArrayList<Node> list = new ArrayList<>();
    public static int n,k, s, x, y;
    public static int[] dx = {0,0,-1,1};
    public static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        map = new int[n+1][n+1];

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] != 0) list.add(new Node(i,j,map[i][j]));
            }
        }

        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        int sec = 0;
        boolean printAns = false;
        while (!list.isEmpty()){
            if(sec == s) {
                bw.write(String.valueOf(map[x][y])+"\n");
                printAns = true;
            }
            int size = list.size();
            Collections.sort(list);
            ArrayList<Node> temp = new ArrayList<>();
            for(int i=0; i<size; i++){
                Node node = list.get(i);
                int x = node.getX();
                int y = node. getY();

                for(int j=0; j<4; j++){
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    if(nx<1 || ny < 1 || nx > n || ny > n) continue;
                    if(map[nx][ny]!=0) continue;
                    map[nx][ny] = node.getVal();
                    temp.add(new Node(nx,ny,node.getVal()));
                }
            }
            sec++;
            list = temp;
        }
        if(!printAns) bw.write(String.valueOf(map[x][y])+"\n");
        bw.flush();
        br.close();
        bw.close();
    }
}