[Baekjoon] 미세먼지 안녕!

👀 문제 설명

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 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

7 8 1

0 0 0 0 0 0 0 9

0 0 0 0 3 0 0 8

-1 0 5 0 0 0 22 0

-1 8 0 0 0 0 0 0

0 0 0 0 0 10 43 0

0 0 5 0 15 0 0 0

0 0 40 0 0 0 20 0

 

예제 출력 1

188

 

예제 입력 2

7 8 2

0 0 0 0 0 0 0 9

0 0 0 0 3 0 0 8

-1 0 5 0 0 0 22 0

-1 8 0 0 0 0 0 0

0 0 0 0 0 10 43 0

0 0 5 0 15 0 0 0

0 0 40 0 0 0 20 0

 

예제 출력 2

188

 

예제 입력 3

7 8 3

0 0 0 0 0 0 0 9

0 0 0 0 3 0 0 8

-1 0 5 0 0 0 22 0

-1 8 0 0 0 0 0 0

0 0 0 0 0 10 43 0

0 0 5 0 15 0 0 0

0 0 40 0 0 0 20 0

 

예제 출력 3

186

 

예제 입력 4

7 8 4

0 0 0 0 0 0 0 9

0 0 0 0 3 0 0 8

-1 0 5 0 0 0 22 0

-1 8 0 0 0 0 0 0

0 0 0 0 0 10 43 0

0 0 5 0 15 0 0 0

0 0 40 0 0 0 20 0

 

예제 출력 4

178

 

예제 입력 5

7 8 5

0 0 0 0 0 0 0 9

0 0 0 0 3 0 0 8

-1 0 5 0 0 0 22 0

-1 8 0 0 0 0 0 0

0 0 0 0 0 10 43 0

0 0 5 0 15 0 0 0

0 0 40 0 0 0 20 0

 

예제 출력 5

172

 

예제 입력 6

7 8 20

0 0 0 0 0 0 0 9

0 0 0 0 3 0 0 8

-1 0 5 0 0 0 22 0

-1 8 0 0 0 0 0 0

0 0 0 0 0 10 43 0

0 0 5 0 15 0 0 0

0 0 40 0 0 0 20 0

 

예제 출력 6

71

 

예제 입력 7

7 8 30

0 0 0 0 0 0 0 9

0 0 0 0 3 0 0 8

-1 0 5 0 0 0 22 0

-1 8 0 0 0 0 0 0

0 0 0 0 0 10 43 0

0 0 5 0 15 0 0 0

0 0 40 0 0 0 20 0

 

예제 출력 7

52

 

예제 입력 8

7 8 50

0 0 0 0 0 0 0 9

0 0 0 0 3 0 0 8

-1 0 5 0 0 0 22 0

-1 8 0 0 0 0 0 0

0 0 0 0 0 10 43 0

0 0 5 0 15 0 0 0

0 0 40 0 0 0 20 0

 

예제 출력 8

46

 

✍🏻풀이

구현 문제이다.

 

먼저, T초동안 미세먼지가 확산되고, 공기청정기가 가동되므로, while문으로 T가 0이 아닐동안 미세먼지 확산과 공기청정기 가동이 반복된다. (T--)

 

[미세먼지 확산]

spread() 메서드는 미세먼지를 확산시켜주는 메서드이다.

먼저, 미세먼지가 있는 칸이 확산 가능한 칸이라면, dusts 배열에 넣는다. (만약, A[r][c]가 5보다 작다면, 해당 칸은 미세먼지가 확산되지 않는다. -> 확산량이 A[r][c] / 5이기 때문에)

이제 dusts 배열과 spreadA 배열을 사용해 미세먼지를 확산시켜주면 된다.

미세먼지 확산은 아래와 같은 규칙이 있다.

1. (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.

2. 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.

3. 확산되는 양은 Ar,c/5이고 소수점은 버린다.

4. (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.

이 때, 각 칸에 미세먼지가 확산되는 양을 저장해주는 2차원 배열 spreadA를 사용해 미세먼지 확산량을 저장해준다.

아래 그림을 예로 들면,

spreadA[3][3] = {

    { 0, 9, 0 },

    { 9, -36, 9 },

    { 0, 9, 0 }

};

과 같은 spreadA 배열을 갖게 되는 것이다. 그러므로, 미세먼지 확산 이후의 A배열은 다음과 같은 식을 갖는다.

A[r][c] = A[r][c] + spreadA[r][c];

 

[공기청정기 가동]

미세먼지를 확산시켰다면, 이제 공기청정기를 가동시킬 차례이다.

공기청정기를 가동시키는 메서드는 runAirCleaner이다.

위쪽 공기청정기의 바람은 반시계 방향으로, 아래쪽 공기청정기의 바람은 시계 방향으로 불기 때문에 runAirCleaner의 매개변수로 위쪽인지 아래쪽인지를 전달하는 type을 보낸다.

바람의 방향에 따라 미세먼지가 이동할 좌표인 nextR, nextC를 구하고, 만약 (nextR, nextC)가 범위를 벗어난다면, 방향을 바꿔줘야 한다. 이 때, type이 0이라면 반시계 방향으로, 1이라면 시계 방향으로 바꿔주고, runAirCleaner를 재귀 호출한다. (이 때, 매개변수는 같은걸 보낸다.)

만약, (nextR, nextC)가 범위를 벗어나지 않으면, 미세먼지를 순환시킨다.

(r, c)의 미세먼지를 (nextR, nextC)로 보내고, (nextR, nextC)의 미세먼지는 temp에 저장한 후, 다음 재귀로 보낼 매개변수 temp에 보낸다.

미세먼지 순환이 끝다면, 공기 청정기로 들어온 미세먼지는 정화되므로, 공기청정기 위치를 -1로 설정해준다.

 

while 문이 끝났다면, T초동안 미세먼지가 확산되고, 공기청정기가 가동된 게 끝났으므로, 이차원 배열 A의 미세먼지 값들을 다 더해 출력한다.

 

코드

package boj;

// 미세먼지 안녕! (https://www.acmicpc.net/problem/17144 )

import java.util.*;
import java.io.*;

public class BOJ_17144 {
	
	private static int[] dr = { 0, 1, 0, -1 };
	private static int[] dc = { 1, 0, -1, 0 };
	private static int R, C, T;
	private static int[][] spreadA; // 각 위치에 미세먼지가 얼마나 더해지고 빼지는지 저장하는 배열
	private static int[][] A; // 미세먼지 확산 전 배열
	private static ArrayList<int[]> dusts = new ArrayList<>(); // 미세먼지가 있는 위치를 저장하는 배열
	private static int[] airCleaner;

	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());
		
		// input
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		
		A = new int[R + 1][C + 1];
		boolean getAirCleaner = false;
		for (int r = 1; r <= R; r++) {
			st = new StringTokenizer(br.readLine());
			
			for (int c = 1; c <= C; c++) {
				A[r][c] = Integer.parseInt(st.nextToken());
				
				if (!getAirCleaner && A[r][c] == -1) {
					getAirCleaner = true;
					airCleaner = new int[] { r, c };
				}
			}
		}
		
		// solve
		// T초동안 미세먼지 확산 & 공기청정기 가동
		while (T != 0) {
			// 1초동안 이뤄지는 일들 작성
			spread(); // 미세먼지 확산
		
			runAirCleaner(airCleaner[0], airCleaner[1], 0, 0, 0); // 위쪽 공기청정기 가동
			runAirCleaner(airCleaner[0] + 1, airCleaner[1], 1, 0, 0); // 아래쪽 공기청정기 가동

			T--;
		}
		
		int ans = 0;
		for (int r = 1; r <= R; r++) {
			for (int c = 1; c <= C; c++) {
				if (A[r][c] != -1) ans += A[r][c];
			}
		}
		bw.write(ans + "\n");
		
		bw.flush();
		bw.close();
	}
	
	private static void spread() {
		spreadA = new int[R + 1][C + 1];
		
		// 미세먼지가 있는 좌표 가져오기
		dusts.clear();
		for (int r = 1; r <= R; r++) {
			for (int c = 1; c <= C; c++) {
				if (A[r][c] != 0 && A[r][c] != -1) // 미세먼지가 있는 공간
					if (A[r][c] >= 5) // 미세먼지가 5 이상인 경우에만 확산한다. (확산량이 A[r][c] / 5 이기 때문에)
						dusts.add(new int[] { r, c });
			}
		}
		
		for (int[] dust : dusts) {
			int spreadNum = 0;
			int spreadDust = A[dust[0]][dust[1]] / 5;
			
			for (int dir = 0; dir < 4; dir++) {
				int adjX = dust[0] + dr[dir];
				int adjY = dust[1] + dc[dir];
				
				// 유효한 범위가 아니거나, 공기청정기가 있는 곳이면 다음으로 넘긴다.
				if (adjX < 1 || adjX > R || adjY < 1 || adjY > C || A[adjX][adjY] == -1) continue;
				
				// 유효한 범위라면
				spreadNum++; // 인접한 몇 개의 칸에 미세먼지가 확산되는가?
				spreadA[adjX][adjY] += spreadDust; // 미세먼지 확산 정보 담기
			}
			
			spreadA[dust[0]][dust[1]] -= spreadDust * spreadNum; // dust[0], dust[1] 위치의 미세먼지에서 확산된 미세먼지만큼을 빼준다.
		}
		
		// 미세먼지 확산
		for (int r = 1; r <= R; r++)
			for (int c = 1; c <= C; c++)
				A[r][c] += spreadA[r][c];
	}
	
	private static void runAirCleaner(int r, int c, int type, int dir, int temp) {
		int nextR = r + dr[dir];
		int nextC = c + dc[dir];
		
		// 범위를 벗어나면 방향을 바꿔준다.
		if (nextR < 1 || nextR > R || nextC < 1 || nextC > C) {
			if (type == 0) {
				if (dir - 1 < 0)
					dir = 3;
				else
					dir -= 1;
			}
			else dir = (dir + 1) % 4; // 시계방향으로
			
			runAirCleaner(r, c, type, dir, temp); // 방향을 바꿔서 다시 돌린다.
			return;
		}
		else {
			// 범위를 벗어나지 않으면, 미세먼지 순환
			int tempNum = A[nextR][nextC];
			A[nextR][nextC] = temp;
			
			if (type == 0 && nextR == airCleaner[0] && nextC == airCleaner[1]) return;
			else if (type == 1 && nextR == airCleaner[0] + 1 && nextC == airCleaner[1]) return;
			
			runAirCleaner(nextR, nextC, type, dir, tempNum);			
		}
		
		// 공기 청정기로 들어온 미세먼지는 정화된다. (사라지고, 공기청정기로 다시 표시해주기) 
		A[airCleaner[0]][airCleaner[1]] = A[airCleaner[0] + 1][airCleaner[1]] = -1;
	}

}