백준 17144 : 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

[ 문제풀이 ]

이번에도 역시 주어진 조건대로 시뮬레이션하는 문제이다.

공기 청정기에 의해 미세먼지들이 한 칸씩 이동하는 것을 경우에 따라 나눠서 구현하는 것도 가능하지만 위, 아래 청정기의 방향을 따로 변수를 만들어 dfs를 돌리는 식으로 하면 훨씬 더 직관적이고 수월하게 구현할 수 있다.

​또한, 모든 미세먼지가 확산되고 난 후 미세먼지 전체 값을 갱신해줘야 하기 때문에 2개의 2차원 배열을 사용하여 미세먼지를 누적시킨다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static int r, c, t, robotR;
	static int[][] map, temp;

	static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; //공기 청정기 윗 부분
	static int[][] dir2 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; //공기 청정기 아랫 부분


	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		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];
		temp = new int[r][c];
		for (int i = 0; i < r; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < c; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == -1 && robotR == 0) {
					robotR = i; //로봇 청소기의 위쪽 행
				}
			}
		}
		
		while (t-- > 0) {
			//미세먼지들을 찾아서 확산시킴
			findDust();
			//공기 청정기를 작동시킴
			operateRobot();
			//temp -> map
			copyDust();
		}

		bw.write(getDust() + "\n");
		bw.flush();bw.close();br.close();
	}

	public static void findDust() {
		for (int i = 0; i < r; ++i) {
			for (int j = 0; j < c; ++j) {
				if (map[i][j] == 0) continue;
				spreadDust(i, j);
			}
		}
	}

	public static void spreadDust(int y, int x) {
		int cnt = 0;
		int dust = map[y][x] / 5;

		//퍼뜨리는 미세먼지 양이 1보다 적으면 확산할 필요 없음
		//바로 temp에 저장하고 return
		if (dust < 1) {
			temp[y][x] += map[y][x];
			return;
		}

		for (int d = 0; d < 4; ++d) {
			int ny = y + dir[d][0];
			int nx = x + dir[d][1];

			if (ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
			if (map[ny][nx] == -1) continue;
			
			cnt++;
			temp[ny][nx] += dust;
		}

		temp[y][x] += map[y][x] - (dust * cnt);
	}

	public static void operateRobot() {
		temp[robotR - 1][0] = temp[robotR - 2][0];
		moveUpRobot(robotR - 2, 0, 0);
		temp[robotR][1] = 0;
		temp[robotR][0] = -1;
		
		temp[robotR + 2][0] = temp[robotR + 3][0];
		moveDownRobot(robotR + 3, 0, 0);
		temp[robotR + 1][1] = 0;
		temp[robotR + 1][0] = -1;
	}

	//위, 오른쪽, 아래, 왼쪽 순서로 탐색
	public static void moveUpRobot(int y, int x, int d) {
		int ny = y + dir[d][0];
		int nx = x + dir[d][1];
		
		//영역을 벗어나거나 로봇 청소기 위쪽 부분을 벗어나면 방향을 바꿔줌
		if (ny < 0 || nx < 0 || ny >= robotR + 1 || nx >= c) {
			moveUpRobot(y, x, d + 1);
			return;
		}

		//로봇 청소기 위쪽에 도달하면 종료
		if (ny == robotR && nx == 0) return;
		
		temp[y][x] = temp[ny][nx];
		moveUpRobot(ny, nx, d);
	}
	
	//아래, 오른쪽, 위, 왼쪽 순서로 탐색
	public static void moveDownRobot(int y, int x, int d) {
		int ny = y + dir2[d][0];
		int nx = x + dir2[d][1];

		//영역을 벗어나거나 로봇 청소기 아래쪽 부분을 벗어나면 방향을 바꿔줌
		if (ny < robotR + 1 || nx < 0 || ny >= r || nx >= c) {
			moveDownRobot(y, x, d + 1);
			return;
		}
		
		//로봇 청소기 아래쪽에 도달하면 종료
		if (ny == robotR + 1 && nx == 0) return;
	
		temp[y][x] = temp[ny][nx];
		moveDownRobot(ny, nx, d);
	}
	

	public static void copyDust() {
		for (int i = 0; i < r; ++i) {
			for (int j = 0; j < c; ++j) {
				map[i][j] = temp[i][j];
				temp[i][j] = 0;
			}
		}
	}
	
	public static int getDust() {
		int totalDust = 0;
		for (int i = 0; i < r; ++i) {
			for (int j = 0; j < c; ++j) {
				if (map[i][j] == -1) continue;
				totalDust += map[i][j];
			}
		}
		return totalDust;
	}
}