백준 18405 - 경쟁적 전염

문제

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

리뷰

BFS를 이용하여 풀이할 수 있는 간단한 문제였다.

Point라는 클래스를 정의하여 BFS 탐색시 바이러스 값, level를
관리할 수 있도록 하였다. 우선 입력을 받으며 바이러스를 Point를
이용해 List에 담아준다. 그 다음 List를 바이러스 값을 기준으로
오름차순 정렬한 후 BFS시 사용할 큐에 앞에서부터 삽입해준다.
이 연산을 통해 탐색시 바이러스 값이 작은 경우부터 먼저 전파가
진행된다.

이후, S 레벨 이내에서 BFS 탐색을 진행하며 바이러스가 전파되지
않은 곳에 바이러스를 전파시켜주면 답을 도출할 수 있다.

로직의 시간복잡도는 BFS의 $O(N^2)$으로 수렴하고 이는 $N=200$인
최악의 경우에도 제한 조건 1초를 무난히 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.parseInt;

public class Main {
    static int N, K;
    static int[][] map;
    static Queue<Point> queue = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = parseInt(st.nextToken());
        K = parseInt(st.nextToken());

        map = new int[N][N];

        List<Point> list = new ArrayList<>();

        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c] = parseInt(st.nextToken());
                if (map[r][c] != 0)
                    list.add(new Point(r, c, map[r][c], 0));
            }
        }

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

        list.sort(Comparator.comparingInt(p -> p.val));
        for (Point point : list) {
            queue.offer(point);
        }

        bfs(S);
        System.out.println(map[X][Y]);
        br.close();

    }

    static void bfs(int S) {
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        int nr, nc;
        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            if (cur.level + 1 > S) break;

            for (int i = 0; i < dr.length; i++) {
                nr = cur.r + dr[i];
                nc = cur.c + dc[i];

                if (nr < 0 || nr >= N || nc < 0 || nc >= N)
                    continue;

                if (map[nr][nc] == 0) {
                    map[nr][nc] = cur.val;
                    queue.offer(new Point(nr, nc, cur.val, cur.level + 1));
                }
            }
        }
    }

    static class Point {
        int r, c, val, level;

        public Point(int r, int c, int val, int level) {
            this.r = r;
            this.c = c;
            this.val = val;
            this.level = level;
        }
    }
}

결과