[BOJ] 16920 확장 게임 (JAVA)

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

16920번: 확장 게임

BFS 문제입니다.

S의 값이 최악의 경우 10억으로, 시간초과를 유도하는 문제입니다.

S의 값을 인위적으로 제어함으로 시간초과를 벗어났습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int N, M, P;
    static int[] S, cnt;
    static int[] dr = { -1,  0,  1,  0 };
    static int[] dc = {  0,  1,  0, -1 };
    static char[][] arr;
    static Queue<Pos>[] q;

    public static void main(String[] args) throws Exception {

        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        S = new int[P + 1];
        q = new LinkedList[P + 1];
        cnt = new int[P  + 1];
        for (int i = 1; i <= P; i++) {
            q[i] = new LinkedList<>();
        }
        arr = new char[N][M];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= P; i++) {
            S[i] = Integer.parseInt(st.nextToken());
            if(Math.max(N, M) < S[i]) S[i] = Math.max(N, M);
        }
        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if(0 < arr[i][j] - '0' && arr[i][j] - '0' < 10) {
                    q[arr[i][j] - '0'].offer(new Pos(i, j));
                    cnt[arr[i][j] - '0']++;
                }
            }
        } // end of input

        boolean flag = true;

        while(flag) {

            flag = false;

            for (int i = 1; i <= P; i++) {

                for (int dist = 0; dist < S[i]; dist++) {

                    int size = q[i].size();

                    while(size-- > 0) {

                        Pos p = q[i].poll();

                        for (int dir = 0; dir < 4; dir++) {

                            int nr = p.row + dr[dir];
                            int nc = p.col + dc[dir];

                            if(0 <= nr && nr < N && 0 <= nc && nc < M && arr[nr][nc] == '.') {

                                flag = true;
                                arr[nr][nc] = (char) (i + '0');
                                q[i].offer(new Pos(nr, nc));
                                cnt[i]++;

                            }

                        }

                    }

                }

            }

        }

        for (int i = 1; i <= P; i++) {
            sb.append(cnt[i]).append(" ");
        }
        System.out.print(sb.toString());

    }

    static class Pos {

        int row, col;

        public Pos(int row, int col) {

            this.row = row;
            this.col = col;

        }

    }

}