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

출처 : www.acmicpc.net/problem/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. 확산 시키며 갱신하기 

3. 공기청정기 작동 시키기

코드

package 알고리즘스터디문제;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 미세먼지안녕_17144 {

	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static int R, C, T;
	static int[][] map;
	static Queue<Dust> dusts = new LinkedList<>();
	static int[] Cleaner = new int[2]; // 공기청정기 위치 [0] = 상부 , [1] = 하부
	static int answer = 0;

	public static class Dust {
		int r;
		int c;
		int amount;

		public Dust(int r, int c, int amount) {
			this.r = r;
			this.c = c;
			this.amount = amount;
		}

	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		R = sc.nextInt(); // row
		C = sc.nextInt(); // column
		T = sc.nextInt(); // seconds

		map = new int[R][C];
		int idx = 0;

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				map[i][j] = sc.nextInt();

				// 공기청정기의 위치
				if (map[i][j] == -1) {
					Cleaner[idx++] = i;
				}
			}
		}

		// 0. 1번과 2번을 계속 반복하는거 1초마다 한번씩 - 매초
		for (int t = 0; t < T; t++) {
			// 1. 미세먼지가 있는 곳 ( 좌표 , 값 ) - original -> 큐에 다 넣어 두기
			makeQueue();

			// 2. map = 확산 시키며 갱신 [ 기준은 큐에 있는거 하나씩 꺼내면서 ]
			spread();

			// test

			// 3. 공기 청정기 작동 시켜서 미세먼지 이동 시키기
			// * 주의 할점 : 공기 청정기 부분과 같은 위치에 들어오는 미세먼지들은 사라짐
			play();

		}
		for ( int i=0; i<R; i++) {
			for ( int j=0; j<C; j++) {
				if ( map[i][j] != -1 && map[i][j] !=0 ) answer += map[i][j];
			}
		}
		System.out.println(answer);
	}

	private static void play() {
		// TODO Auto-generated method stub
		int top = Cleaner[0];
		int down = Cleaner[1];

		// cleaner 상부 시계 반대 방향

		// 위쪽 아래로 당기기
		for (int i = top-1; i > 0; i--) {
			map[i][0] = map[i - 1][0];
		}
		// 왼쪽으로 당기기
		for (int i = 0; i < C - 1; i++) {
			map[0][i] = map[0][i + 1];
		}
		// 우측 상단에서 아래꺼 당기기
		for (int i = 0; i < top; i++) {
			map[i][C - 1] = map[i + 1][C - 1];
		}
		// 가장 오른쪽에서 왼쪽에 있는거 당기기
		for (int i = C - 1; i > 1; i--) {
			map[top][i] = map[top][i-1];
			if ( i== 2) map[top][i-1] =0;
		}
		
		// 공기청정기 위치에 있는 애 공기없애기
		map[top][0] = -1;
		// cleaner 하부 시계 방향
		// 아래있는거 위로 당기기
		for (int i = down+1; i < R-1; i++) {
			map[i][0] = map[i + 1][0];
		}
		// 왼쪽으로 당기기
		for (int i = 0; i < C - 1; i++) {
			map[R-1][i] = map[R-1][i + 1];
		}
		// 아래로 내리기
		for (int i = R-1; i > down; i--) {
			map[i][C - 1] = map[i - 1][C - 1];
		}
		// 가장 오른쪽에서 왼쪽에 있는거 당기기
		for (int i = C - 1; i > 1; i--) {
		
			map[down][i] = map[down][i - 1] ;
			if ( i== 2) map[down][i-1] =0;
		}
		map[down][0] = -1;
	}

	public static void print() {
		// TODO Auto-generated method stub
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

	private static void spread() {
		// 기존 큐에 있는거 하나씩 꺼내면서 확산 시키기
		while (!dusts.isEmpty()) {
			// 하나 꺼내
			Dust cur = dusts.poll();
			int cr = cur.r;
			int cc = cur.c;
			int camount = cur.amount;

			// 주변에 확산시키고, 확산된 갯수 세주자
			int cnt = 0;
			int spread_amount = camount / 5;
			for (int d = 0; d < 4; d++) {
				int nr = dr[d] + cr;
				int nc = dc[d] + cc;

				// 맵 안에 있고 ,공기 청정기가 없는 위치에
				if (isIn(nr, nc) && map[nr][nc] != -1) {
					map[nr][nc] = map[nr][nc] + spread_amount; 
					cnt++;
				}

			}

			// 본인 위치 감소 시키고
			map[cr][cc] = map[cr][cc] - spread_amount * cnt >= 0 ? map[cr][cc] - spread_amount * cnt : 0;
		}

	}

	private static boolean isIn(int nr, int nc) {
		// TODO Auto-generated method stub
		if (nr >= 0 && nr < R && nc >= 0 && nc < C)
			return true;

		return false;
	}

	private static void makeQueue() {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				// 공기 청정기 위치도 아니고, 어떠한 값이 들어왔다면, 행 + 열 + 먼지의 양 저장
				if (map[i][j] != 0 && map[i][j] != -1)
					dusts.add(new Dust(i, j, map[i][j]));
			}
		}
	}

}