Baekjoon 17144 미세먼지 안녕! 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초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

풀이

복잡해 보이는 코드지만, 따로 알고리즘이 필요하지는 않다.

코드를 크게 spread 확산하는 부분, aircleaner 공기청정기가 작동하는 두 부분으로 나누어서 해결하였다.

spread에서는 전체를 완전탐색하면서 그 위치에 먼지가 있고 5보다 클때만 확산하기에 전체를 탐색하면서 배열에 값이 있다면, 그 위치에서 사방으로 퍼질 수 있는지 확인 후, n/5한 값을 옆으로 전달한다. 이때, 문제에서 소수점을 버린다는 조건때문에 나중에 남아있는 먼지를 계산하기에 나머지를 사용하지 않고 더하기를 이용하여 옆으로 퍼진 값을 더해놓는다. 이 값은 잔여 먼지량을 적는데 쓰일것이다.

aircleaner는 사각형의 배열을 돌리는데 사용된다.

참고코드 :

2022.02.09 - [Algorithm/Baekjoon] - Baekjoon 16926 배열 돌리기 1 JAVA

2022.02.09 - [Algorithm/Baekjoon] - Baekjoon 16927 배열 돌리기 2 JAVA

2022.02.09 - [Algorithm/Baekjoon] - Baekjoon 16935 배열 돌리기 3 JAVA

2022.02.10 - [Algorithm/Baekjoon] - Baekjoon 17406 배열 돌리기 4 JAVA

 

코드

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

public class Main {
	public static void spread(int[][] map, int r, int c) {
		int[][] newmap = new int[r + 1][c + 1];
		int[] dx = new int[] { -1, 1, 0, 0 }, dy = new int[] { 0, 0, -1, 1 };
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				if (map[i][j] != -1) {
					int cnt = 0, temp = 0;
					for (int k = 0; k < 4; k++) {
						if (i + dx[k] >= 1 && i + dx[k] <= r && j + dy[k] >= 1 && j + dy[k] <= c) {
							if (map[i + dx[k]][j + dy[k]] != -1 && map[i][j] >= 5) {
								newmap[i + dx[k]][j + dy[k]] += map[i][j] / 5;
								temp += map[i][j] / 5;
							}
						}
					}
					newmap[i][j] += map[i][j] - temp;
				} else
					newmap[i][j] = map[i][j];
			}
		}
		for (int i = 1; i <= r; i++)
			for (int j = 1; j <= c; j++)
				map[i][j] = newmap[i][j];
	}

	public static void aircleaner(int[][] map, int r, int c) {
		int loc = 0;
		for (int i = 1; i <= r; i++)
			if (map[i][1] == -1) {
				loc = i;
				break;
			}
		// 상단
		for (int i = loc - 1; i >= 1; i--)
			map[i][1] = map[i - 1][1];
		for (int j = 1; j <= c - 1; j++)
			map[1][j] = map[1][j + 1];
		for (int i = 1; i <= loc - 1; i++)
			map[i][c] = map[i + 1][c];
		for (int j = c; j >= 2; j--)
			map[loc][j] = map[loc][j - 1];
		map[loc][2] = 0;
		// 하단
		for (int i = loc + 2; i <= r - 1; i++)
			map[i][1] = map[i + 1][1];
		for (int j = 1; j <= c - 1; j++)
			map[r][j] = map[r][j + 1];
		for (int i = r; i >= loc + 1; i--)
			map[i][c] = map[i - 1][c];
		for (int j = c; j >= 2; j--)
			map[loc + 1][j] = map[loc + 1][j - 1];
		map[loc + 1][2] = 0;

	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int r = Integer.parseInt(st.nextToken()), c = Integer.parseInt(st.nextToken()),
				t = Integer.parseInt(st.nextToken());
		int[] cleaner = new int[2];
		int[][] map = new int[r + 1][c + 1];
		for (int i = 1; i <= r; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= c; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		for (int k = 0; k < t; k++) {
			spread(map, r, c);
			aircleaner(map, r, c);
		}
		int sum=0;
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				if(map[i][j]!=-1)
					sum+=map[i][j];
			}
		}
		System.out.println(sum);
	}
}