17144. 미세먼지 안녕!

- 주석으로 설명을 대신한다.

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

public class B_17144_미세먼지안녕 {

	static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int R, C, T;
	static int[][] arr;
	static List<Integer> airCleaner = new ArrayList<>(); // y값만 저장, x는 항상 0
	static Queue<int[]> q = new LinkedList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		arr = new int[R][C];
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < C; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (arr[i][j] >= 5) // 5이상이면 확산가능
					q.offer(new int[] { i, j, arr[i][j] });
				else if (arr[i][j] == -1) // 공기청정기 위치
					airCleaner.add(i);

			}
		}

		bfs(1);

		sb.append(counting());
		System.out.println(sb);
	}

	private static int counting() {
		int count = 0;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (arr[i][j] == -1)
					continue;
				count += arr[i][j];
			}
		}
		return count;
	}

	private static void circle(int time) {
		// 위쪽 반시계
		int y = airCleaner.get(0);
		for (int i = y - 1; i >= 0; i--) // 좌
			arr[i + 1][0] = arr[i][0];
		for (int i = 1; i < C; i++) // 상
			arr[0][i - 1] = arr[0][i];
		for (int i = 1; i <= y; i++) // 우
			arr[i - 1][C - 1] = arr[i][C - 1];
		for (int i = C - 2; i >= 0; i--) // 하
			arr[y][i + 1] = arr[y][i];

		// 공기청정
		arr[y][1] = 0;

		// 아래쪽 시계
		y = airCleaner.get(1);
		for (int i = y + 1; i < R; i++) // 좌
			arr[i - 1][0] = arr[i][0];
		for (int i = 1; i < C; i++) // 하
			arr[R - 1][i - 1] = arr[R - 1][i];
		for (int i = R - 2; i >= y; i--) // 우
			arr[i + 1][C - 1] = arr[i][C - 1];
		for (int i = C - 2; i >= 0; i--) // 상
			arr[y][i + 1] = arr[y][i];

		// 공기청정
		arr[y][1] = 0;

		setting();
		if (time == T)
			return;
		bfs(++time);
	}

	private static void setting() {
		// 다시 공기청정기 표시하기
		for (int i = 0; i < 2; i++) {
			int r = airCleaner.get(i);
			arr[r][0] = -1;
		}

		// Q
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (arr[i][j] >= 5)
					q.offer(new int[] { i, j, arr[i][j] });
			}
		}
	}

	private static void bfs(int time) {
		while (!q.isEmpty()) {
			int[] now = q.poll();
			int y = now[0];
			int x = now[1];
			int weight = now[2] / 5;
			int cnt = 0;
			for (int i = 0; i < 4; i++) {
				int my = y + dir[i][0];
				int mx = x + dir[i][1];
				if (!isArea(my, mx) || arr[my][mx] == -1)
					continue;
				arr[my][mx] += weight;
				cnt++;
			}
			if (cnt > 0)
				arr[y][x] = (arr[y][x] - now[2]) + (now[2] - (weight * cnt));
		}
		circle(time);
	}

	private static boolean isArea(int y, int x) {
		if (x < 0 || y < 0 || y >= R || x >= C)
			return false;
		return true;
	}

}