[Java] 백준 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

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

 

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int R, C, T;
	private static int [][]map, newMap;
	private static AirMachine airMachine;
	private static int []dx= {-1,1,0,0};
	private static int []dy= {0,0,-1,1};

	static class AirMachine {
		int x1, x2;

		public AirMachine(int x1, int x2) {
			super();
			this.x1 = x1;
			this.x2 = x2;
		}

		@Override
		public String toString() {
			return "AirMachine [x1=" + x1 + ", x2=" + x2 + "]";
		}

	}

	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(br.readLine());
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		T=Integer.parseInt(st.nextToken());
		map=new int[R+1][C+1];
		boolean check=false;
		
		for(int r=1;r<=R;r++) {
			st=new StringTokenizer(br.readLine());
			for(int c=1;c<=C;c++) {
				map[r][c]=Integer.parseInt(st.nextToken());
				if(map[r][c]==-1 && !check) {
					airMachine=new AirMachine(r, r+1);
					check=true;
				}
			}
		}
		for(int t=1;t<=T;t++) {
			boolean [][]visited=new boolean[R+1][C+1];
			newMap=new int[R+1][C+1];
			
			// 미세먼지 확산
			for(int r=1;r<=R;r++) {
				for(int c=1;c<=C;c++) {
					if(map[r][c]==0 || visited[r][c]) continue;
					spread(r, c, map[r][c]);
				}
			}
			copyMap(map, newMap);
			
			// 공기청정기 작동
			air();
		}
		
		int result=0;
		for(int r=1;r<=R;r++) {
			for(int c=1;c<=C;c++) {
				if(map[r][c]==0 || map[r][c]==-1) continue;
				result+=map[r][c];
			}
		}
		
		System.out.println(result);
	}

	private static void copyMap(int [][]map, int [][]newMap) {
		for(int r=1;r<=R;r++) map[r]=newMap[r].clone();	// 원래 map에서 확산량을 확인해주려면 원본을 유지해야 하므로 새로운 배열을 만들어서 확산 정보 저장
	}
	private static void spread(int r, int c, int x) {
		int val=x/5;
		int cnt=0;
		
		for(int d=0;d<4;d++) {
			int nx=r+dx[d];
			int ny=c+dy[d];
			
			if(ny==1 && (nx==airMachine.x1 || nx==airMachine.x2)) continue;	// 공기청정기 위치인 경우 그냥 패스
			if(isIn(nx, ny)) {	// 확산 가능한 영역 확인
				cnt++;
				newMap[nx][ny]+=val;
			}
		}
		newMap[r][c]+=map[r][c]-val*cnt;	// 확산되고 남은 부분 저장
	}
	
	private static void air() {	// 공기청정기 작동
		// top
		for(int r=airMachine.x1-1;r>1;r--) {
			map[r][1]=map[r-1][1];
		}
		for(int c=1;c<C;c++) {
			map[1][c]=map[1][c+1];
		}
		for(int r=1;r<airMachine.x1;r++) {
			map[r][C]=map[r+1][C];
		}
		for(int c=C;c>2;c--) {
			map[airMachine.x1][c]=map[airMachine.x1][c-1];
		}
		map[airMachine.x1][2]=0;
		
		// down
		for(int r=airMachine.x2+1;r<R;r++) {
			map[r][1]=map[r+1][1];
		}
		for(int c=1;c<C;c++) {
			map[R][c]=map[R][c+1];
		}
		for(int r=R;r>airMachine.x2;r--) {
			map[r][C]=map[r-1][C];
		}
		for(int c=C;c>2;c--) {
			map[airMachine.x2][c]=map[airMachine.x2][c-1];
		}
		map[airMachine.x2][2]=0;
	}
	
	private static boolean isIn(int r, int c) {
		return r>=1 && r<=R && c>=1 && c<=C;
	}
}

1. 미세먼지 확산

1-1. 확산 정보를 저장할 새로운 배열 newMap을 만들어줍니다.

1-2. 4방향을 탐색하며 확산 가능 영역을 확인하고, 영역을 벗어나거나 공기청정기가 있는 경우는 패스합니다.

1-3. 확산하고 남은 양을 저장합니다.

 

2. 공기청정기 작동

2-1. 위 순환을 구현합니다.

2-2. 아래 순환을 구현합니다.