[백준] G4 17144번 미세먼지 안녕! (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

17144번: 미세먼지 안녕!

[문제] 

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

 

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

 

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

 

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

[입력]

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

[출력]

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

 

 

---

[풀이]

1. 시뮬레이션 문제인 만큼 문제에 주어진 순서대로 동작을 하도록 구현한다.

2. 먼저, 미세먼지가 확산되기 때문에 확산되는 것을 구현한다. (diffusion())

3. 다음으로 공기청정기가 작동하는 것을 구현한다. (cleaner())

4. 위 2, 3번의 과정이 1초에 동작하는 것이기 때문에 주어진 초까지 반복시킨다.

[접근]

1. 공기청정기가 무조건 [i][0]과 [i+1][0]에 주어지는 것을 처리하기 위해서 어떻게 할지 고민했다.

2. 공기청정기가 위, 아래 서로 다른 동작을 하기 때문에 분리해서 생각해줬다.

3. 확산을 어떻게 처리해줘야 할 지 고민했다.

4. 공기청정기의 동작을 어떻게 처리할지 고민했다.

[코드]

package BOJ_gold;

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

public class Main_G4_17144 {
	static int r;
	static int c;
	static int t;
	static int[][] map;
	static int[][] countmap;
	static int bound; // 공기청정기를 기준으로 위 아래 나누기 위한 변수
	static int dust; // 먼지의 개수

	static int[] dr = {1, -1, 0, 0};
	static int[] dc = {0, 0, 1, -1};

	public static void main(String[] args) throws Exception {
		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];

		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)
					bound = i; // i만 저장하는 이유는 무조건 1열에 설치되므로
			}
		}

		// t만큼 반복 시켜준다.
		for (int i = 0; i < t; i++) {
			diffusion(); // 확산시키고
			cleaner(); // 공기청정기 실행
		}
		
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (map[i][j] != -1)
					dust += map[i][j];
			}
		}
		
		System.out.println(dust);
	}

	public static void diffusion() {
		countmap = new int[r][c];
		// map에 바로 적용시키면 다른 곳에서 확산이 되고 난 후 5인 곳에서 확산이 발생할 수 있다.
		// 그를 막아주기 위한 countmap

		for (int i = 0 ; i < r; i++) {
			for (int j = 0; j < c; j++) {
				countmap[i][j] += map[i][j];
				// =이 아니라 +=인 이유는 이전에 확산된 값이 이미 countmap에 들어가 있을 수 있으므로 

				if (map[i][j] < 5) // 5보다 작으면 확산 불가
					continue;

				int diffcnt = map[i][j] / 5; // 확산되는 양은 5로 나눴을때의 몫

				for (int k = 0; k < 4; k++) {
					int nr = i + dr[k];
					int nc = j + dc[k];

					// 공기청정기가 아니고, 범위 안에 들어간다면
					if (nr >= 0 && nr < r && nc >= 0 && nc < c && map[nr][nc] != -1) {
						countmap[nr][nc] += diffcnt; // 주변에는 증가시켜주고
						countmap[i][j] -= diffcnt; // 해당 좌표는 빠진 만큼 감소 시켜준다.
					}
				}
			}
		}

		// countmap에 저장된 값을 map으로 옮겨준다.
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				map[i][j] = countmap[i][j];
			}
		}
	}

	public static void cleaner() {
		countmap = new int[r][c];
		// map에 바로 적용시키면 값이 누락되는 경우가 발생할 수도 있다.
		// 그를 막아주기 위한 countmap
		
		// map을 countmap에 복사
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				countmap[i][j] = map[i][j];
			}
		}

		for (int i = 0; i < 2; i++) {
			int cleaner_r = bound - i; // 공기청정기의 행 (처음엔 밑 부분, 다음은 윗부분)
			int cleaner_c = 0; // 공기청정기의 열은 항상 1

			// 오른쪽으로 쭉
			while (cleaner_c + 1 < c) {
				if (map[cleaner_r][cleaner_c] != -1) // 공기청정기가 아닐때 해야한다.
					countmap[cleaner_r][cleaner_c + 1] = map[cleaner_r][cleaner_c];
				else // 공기청정기라면 해당 위치를 0으로 만들어 준다.
					countmap[cleaner_r][cleaner_c + 1] = 0;
				cleaner_c++;
			}

			// 아래로 or 위로
			if (i == 0) {
				while (cleaner_r + 1 < r) {
					countmap[cleaner_r + 1][cleaner_c] = map[cleaner_r][cleaner_c];
					cleaner_r++;
				}
			}
			else if (i == 1) {
				while (cleaner_r > 0) {
					countmap[cleaner_r - 1][cleaner_c] = map[cleaner_r][cleaner_c];
					cleaner_r--;
				}
			}

			// 왼쪽으로 쭉
			while (cleaner_c > 0) {
				countmap[cleaner_r][cleaner_c - 1] = map[cleaner_r][cleaner_c];
				cleaner_c--;
			}
			// 위로 or 아래로
			if (i == 0) {
				while (cleaner_r > bound - 1) {
					countmap[cleaner_r - 1][cleaner_c] = map[cleaner_r][cleaner_c];
					cleaner_r--;
				}
			}
			else if (i == 1) {
				while (cleaner_r + 1 < bound) {
					countmap[cleaner_r + 1][cleaner_c] = map[cleaner_r][cleaner_c];
					cleaner_r++;
				}
			}
		}
		
		// countmap을 map에 복사
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (map[i][j] == -1) // 공기청정기 위치면 건너뛰기
					continue;
				map[i][j] = countmap[i][j];
			}
		}
	}
}