[백준] 17144번 : 미세먼지 안녕! - 자바(JAVA)

https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

 

문제 해석

R x C 크기의 격자판이 존재합니다.

공기청정기는 항상 1번 열에 설치되어 있고 크기는 두 행을 차지합니다.

 

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

1. 미세먼지가 확산된다. 확산은 미세먼지가 존재하는 모든 칸에서 동시에 일어납니다.

- 미세먼지는 인접한 네 방향으로 확산됩니다.

- 인접한 방향에 공기청정기가 있거나, 칸이 존재하지 않으면 그 방향으로는 확산이 일어나지 않습니다.

- 확산되는 양은 A(r,c) /5이며 소수점은 버립니다.

- 남아있는 미세먼지의 양은 A(r,c) - (A(r,c) / 5 ) * 확산된 방향의 개수입니다.

 

2. 공기청정기가 작동합니다.

- 공기청정기에서는 바람이 나옵니다.

- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환합니다.

- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동합니다.

- 공기청정기에서 부른 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지를 모두 정화됩니다.

 

공기 청전기가 설치된 곳은 -1로 표시합니다.

 

문제 풀이 전 설계

문제가 요구하는데로 쭉 풀면 될것같다고 생각합니다.

먼지의 확산은 BFS를 이용하며 dy,dx 를 적절히 활용한 4방탐색과 배열돌리기가 핵심일것같습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_17144_미세먼지안녕 {

	static class Pos {
		int y;
		int x;

		public Pos(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

		@Override
		public String toString() {
			return "Pos [y=" + y + ", x=" + x + "]";
		}

	}

	static final int AIR_CLEANER = -1;
	static final int DIRECTION = 4;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static int[][] upWind = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };
	static int[][] downWind = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
	static int R, C;
	static int[][] room;
	static Pos aircleanerUp;
	static Pos aircleanerDown;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());

		room = new int[R][C];

		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < C; j++) {
				room[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		findAircleanerLocation();

		for (int i = 0; i < T; i++) {
			// 미세먼지 확산
			dustBFS();
			workAircleaner();
		}
		int sum = 0;

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (room[i][j] == AIR_CLEANER) {
					continue;
				}
				sum += room[i][j];
			}

		}
		System.out.println(sum);

	}

	private static void findAircleanerLocation() {
		outer: for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (room[i][j] != AIR_CLEANER) {
					continue;
				}
				aircleanerUp = new Pos(i, j);
				aircleanerDown = new Pos(i + 1, j);
				break outer;
			}
		}
	}

	private static void dustBFS() {
		Queue<Pos> bfsQ = new LinkedList<Pos>();
		List<Pos> tempPosList = new ArrayList<Pos>();
		int[][] tempRoom = new int[R][C];

		// 초기 확산을 위해 넣어주기
		for (int y = 0; y < R; y++) {
			for (int x = 0; x < C; x++) {
				if (room[y][x] == AIR_CLEANER) {
					tempRoom[y][x] = AIR_CLEANER;
					continue;
				}
				if (room[y][x] == 0) {
					continue;
				}
				bfsQ.add(new Pos(y, x));
			}
		}

		while (!bfsQ.isEmpty()) {
			Pos temp = bfsQ.poll();
			int count = 0;
			for (int k = 0; k < DIRECTION; k++) {
				int tempY = temp.y + dy[k];
				int tempX = temp.x + dx[k];

				if (!isValid(tempY, tempX)) {
					continue;
				}
				count++;
				tempPosList.add(new Pos(tempY, tempX));
			}
			int spreadSize = room[temp.y][temp.x] / 5;
			int remainDust = room[temp.y][temp.x] - spreadSize * count;

			tempRoom[temp.y][temp.x] += remainDust;
			for (Pos e : tempPosList) {
				tempRoom[e.y][e.x] += spreadSize;
			}

			tempPosList.clear();

		}

		// room = tempRoom.clone();
		copyArray(tempRoom);

	}

	private static boolean isValid(int tempY, int tempX) {
		return (tempY >= 0 && tempX >= 0 && tempY < R && tempX < C && room[tempY][tempX] != AIR_CLEANER);
	}

	private static void copyArray(int[][] tempRoom) {
		for (int y = 0; y < R; y++) {
			for (int x = 0; x < C; x++) {
				room[y][x] = tempRoom[y][x];
			}
		}
	}

	private static void showArray() {
		for (int y = 0; y < R; y++) {
			for (int x = 0; x < C; x++) {
				System.out.print(room[y][x] + " ");
			}
			System.out.println();
		}
	}

	private static void workAircleaner() {
		// 위의 바람 반시계방향
		int count = 0;
		Pos aircleanerPos = aircleanerUp;
		int currentY = aircleanerPos.y;
		int currentX = aircleanerPos.x;
		List<Pos> tempPosList = new ArrayList<Pos>();
		while (true) {

			int[] tempArray = upWind[count];
			int tempY = currentY + tempArray[0];
			int tempX = currentX + tempArray[1];

			if (!isValid(tempY, tempX)) {
				count++;
				if (count == 4) {
					break;
				}
				continue;
			}

			currentY = tempY;
			currentX = tempX;

			tempPosList.add(new Pos(currentY, currentX));
		}

		int lastIndex = tempPosList.size() - 1;
		Pos pre = tempPosList.get(lastIndex);
		
		Pos lastCurrent = null;
		for (int i = lastIndex - 1; i >= 0; i--) {
			Pos current = tempPosList.get(i);
			room[pre.y][pre.x] = room[current.y][current.x];
			pre = current;
			lastCurrent = current;
		}
		room[lastCurrent.y][lastCurrent.x] = 0;

		// static int[][] upWind = {{0,1},{-1,0},{0,-1},{1,0}};

		// 아래 바람 시계방향
		count = 0;
		aircleanerPos = aircleanerDown;
		currentY = aircleanerPos.y;
		currentX = aircleanerPos.x;
		tempPosList = new ArrayList<Pos>();
		while (true) {
			int[] tempArray = downWind[count];
			int tempY = currentY + tempArray[0];
			int tempX = currentX + tempArray[1];

			if (!isValid(tempY, tempX)) {
				count++;
				if (count == 4) {
					break;
				}
				continue;
			}

			currentY = tempY;
			currentX = tempX;

			tempPosList.add(new Pos(currentY, currentX));
		}

		lastIndex = tempPosList.size() - 1;
		pre = tempPosList.get(lastIndex);
		lastCurrent = null;
		for (int i = lastIndex - 1; i >= 0; i--) {
			Pos current = tempPosList.get(i);
			room[pre.y][pre.x] = room[current.y][current.x];
			pre = current;
			lastCurrent = current;
		}
		room[lastCurrent.y][lastCurrent.x] = 0;

	}
}