미세먼지 안녕!


백준 [17144] 미세먼지 안녕!

문제보기
Alt text

풀이

  • 시뮬레이션
  • checkTime() : 주어진 시간 동안 미세먼지 확산과 공기청정기 작동
  • microDiff() : 확산된 미세먼지에 대해선 따로 diff에 저장해놓고 확산이 끝나면 map에 추가
  • workMachine() : 공기청정기 위쪽과 아래쪽에 대해 각각 반시계, 시계방향으로 작동

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int R, C, T;
	static int[][] map;
	static int ans;
	static List<int[]> machine;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

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

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		map = new int[R][C];
		machine = new ArrayList<>();
		ans = 0;

		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				int num = Integer.parseInt(st.nextToken());
				map[i][j] = num;
				if (num < 0)
					machine.add(new int[] { i, j });
				else if (num > 0) {
					ans += num;
				}
			}
		}

		checkTime();
		System.out.println(ans);
	}

	public static void checkTime() {
		while (T != 0) {
			microDiff();
			workMachine();
			T--;
		}
	}

	public static void microDiff() {
		List<int[]> diff = new ArrayList<>();
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (map[i][j] > 0) {
					int chk = 0;
					int amount = map[i][j] / 5;
					for (int k = 0; k < 4; k++) {
						int x = i + dx[k];
						int y = j + dy[k];

						if (isRange(x, y) && map[x][y] >= 0) {
							diff.add(new int[] { x, y, amount });
							ans += amount;
							chk++;
						}
					}
					int after = map[i][j] - amount * chk;
					ans -= Math.abs(after - map[i][j]);
					map[i][j] = after;
				}
			}
		}

		for (int i = 0; i < diff.size(); i++) {
			int[] dust = diff.get(i);
			int x = dust[0];
			int y = dust[1];
			int a = dust[2];
			map[x][y] += a;
		}
	}

	public static void workMachine() {
		// 위쪽 : 반시계
		int[][] newMap = new int[R][C];
		int[] up = machine.get(0);
		for (int i = 0; i <= up[0]; i++) {
			for (int j = 0; j < C; j++) {
				if (up[0] == i) { // →
					if (j != 0 && j != C - 1)
						newMap[i][j + 1] = map[i][j];
				}
				if (j == C - 1) { // ↑
					if (i != 0)
						newMap[i - 1][j] = map[i][j];
				}
				if (i == 0) { // ←
					if (j != 0)
						newMap[i][j - 1] = map[i][j];
				}
				if (j == 0 && map[i][j] > 0) { // ↓
					if (up[0] - 1 == i)
						ans -= map[i][j];
					else
						newMap[i + 1][j] = map[i][j];
				}

				if (i > 0 && i < R - 1 && i != up[0] && j > 0 && j < C - 1)
					newMap[i][j] = map[i][j];
			}
		}
		// 아래쪽 : 시계
		int[] down = machine.get(1);
		for (int i = down[0]; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (down[0] == i) { // →
					if (j != 0 && j != C - 1)
						newMap[i][j + 1] = map[i][j];
				}
				if (j == C - 1) { // ↓
					if (i != R - 1)
						newMap[i + 1][j] = map[i][j];
				}
				if (i == R - 1) { // ←
					if (j != 0)
						newMap[i][j - 1] = map[i][j];
				}
				if (j == 0 && map[i][j] > 0) { // ↑
					if (down[0] + 1 == i)
						ans -= map[i][j];
					else
						newMap[i - 1][j] = map[i][j];
				}

				if (i > 0 && i < R - 1 && i != down[0] && j > 0 && j < C - 1)
					newMap[i][j] = map[i][j];
			}
		}
		newMap[up[0]][up[1]] = -1;
		newMap[down[0]][down[1]] = -1;
		map = newMap;
	}

	public static boolean isRange(int x, int y) {
		return x >= 0 && y >= 0 && x < R && y < C;
	}
}