[BOJ 18405] 경쟁적 전염 (Java, BFS)

---

문제 링크

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

18405번: 경쟁적 전염

---

풀이

- N * N 행렬 주어짐 (K 는 바이러스 번호인데, 사용하지 않음)

- 상,하,좌,우 격자형 그래프 탐색 문제

- 아래 조건에 따라 바이러스는 번호와 초에 따라 정렬된 상태에서 탐색이 진행되야 함 (*실수 부분)

단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다

- 따라서 Java에서 제공하는 우선 순위 큐(PriorityQueue) 로 바이러스 번호와 초 값으로 오름차순 정렬 처리할 수 있도록 하면 원하는 정답을 구할 수 있음

 

참고

https://dev-ljw1126.tistory.com/62

[Java]Comparable 과 Comparator 인터페이스

---

제출 코드

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

public class Main {
   static int N, K, S, X, Y;

    static int[][] FIELD;

    static int[][] DIRECTION = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static class Virus {
        int x;
        int y;
        int num;

        int timing;

        public Virus(int x, int y, int num, int timing) {
            this.x = x;
            this.y = y;
            this.num = num;
            this.timing = timing;
        }
    }

    static void input() 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());

        FIELD = 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++) {
                FIELD[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

        S = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());
    }

    static void bfs() {
        Queue<Virus> que = new PriorityQueue<>((a, b) -> {
           if(a.timing == b.timing) return a.num - b.num;
           else return a.timing - b.timing;
        });

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(FIELD[i][j] != 0) {
                    que.add(new Virus(i, j, FIELD[i][j], 0));
                }
            }
        }

        while(!que.isEmpty()) {
            Virus v = que.poll();
            if(v.timing == S) break;

            for(int i = 0; i < 4; i++) {
                int nx = v.x + DIRECTION[i][0];
                int ny = v.y + DIRECTION[i][1];

                if(nx < 1 || ny < 1 || nx > N || ny > N) continue;
                if(FIELD[nx][ny] != 0) continue;

                FIELD[nx][ny] = v.num;
                que.add(new Virus(nx, ny, v.num, v.timing + 1));
            }
        }
    }

    static void pro() {
        bfs();

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

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}