[백준/BOJ][JAVA] 18405 - 경쟁적 전염

문제

18405번: 경쟁적 전염

📒 문제

초기배열

N*N 크기의 시험관에 바이러스는 1~K까지의 종류가 들어있다. 이때, 모든 바이러스는 1초마다 상, 하, 좌, 우로 번호가 낮은 순서대로 증식한다. 단, 바이러스가 이미 존재하는 칸에는 증식할 수 없다.

 

📒 해결방법

우선적으로 input을 받을 때, 0이 아닌 수가 들어오면 PriorityQueue에 넣었다.

이런식으로 x좌표, y좌표, 그리고 해당 배열의 값을 넣어서 그 값으로 정렬해서 낮은 순으로 PriorityQueue에서 꺼내서 bfs를 돌리는 문제였다.

📒 소스 코드

 

package BOJ.Simulation;

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

public class boj18405_경쟁적전염 {
    static int N, K;
    static int[][] map;
    static PriorityQueue<Pair> q;
    static int[] dx = { 1, 0, -1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static int time;
    static int S, X, Y;
    static boolean[][] visit;

    static class Pair implements Comparable<Pair> {
        int x;
        int y;
        int number;

        public Pair(int x, int y, int number) {
            this.x = x;
            this.y = y;
            this.number = number;
        }

        @Override
        public int compareTo(Pair o) {
            return this.number > o.number ? 1 : -1;

        }
    }

    public static void main(String[] args) throws Exception {
        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 + 1][N + 1];
        visit = new boolean[N + 1][N + 1];
        q = new PriorityQueue<>();
        time = 0;
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j < N + 1; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] != 0) {
                    q.offer(new Pair(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());

        if (q.isEmpty()) {
            System.out.println(0);
        } else {

            while (true) {
                if (S == 0) {
                    System.out.println(map[X][Y]);
                    break;
                }
                bfs();

                time++;

                if (q.size() == 0) {
                    for (int i = 1; i < N + 1; i++) {
                        for (int j = 1; j < N + 1; j++) {
                            if (map[i][j] != 0 && visit[i][j] == false) {
                                for (int k = 0; k < 4; k++) {
                                    int nx = i + dx[k];
                                    int ny = j + dy[k];
                                    if (isWall(nx, ny)) {
                                        if (map[nx][ny] == 0)
                                            q.offer(new Pair(i, j, map[i][j]));
                                    }
                                }

                            }
                        }
                    }
                }

                if (time == S || q.isEmpty()) {
                    System.out.println(map[X][Y]);
                    break;
                }

            }
        }

    }

    static void bfs() {
        while (!q.isEmpty()) {
            Pair cur = q.poll();

            visit[cur.x][cur.y] = true;
            for (int k = 0; k < 4; k++) {
                int nx = cur.x + dx[k];
                int ny = cur.y + dy[k];
                if (isWall(nx, ny)) {
                    if (map[nx][ny] == 0) {
                        if (visit[nx][ny] == false) {
                            map[nx][ny] = map[cur.x][cur.y];
                        }
                    }
                }
            }
        }
    }

    static boolean isWall(int x, int y) {
        if (x > 0 && x < N + 1 && y > 0 && y < N + 1)
            return true;
        return false;
    }
}

[리뷰]

 

---

예외처리를 제대로 안해서 계속 틀렸었다..

사실 PriorityQueue를 쓰면 내가 큐에 넣을 때마다 바로 정렬이 갱신되버려서

증식된 바이러스 자체를 이후에 pq에 넣어줘야했다.

다음에 제대로 깔끔하게 풀어봐야겠다😢