[Java] BOJ17144, 백준 - 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

 

코테 기출에 시뮬레이션 문제이다보니 할게 아주아주 많은 정말 귀찮은 문제였다.
하지만 함수를 만들어서 절차에 따라서 진행해주니 해결할 수 있었다.

해야 할 일
1. 먼지 확산시키기
2. 공기청정기로 공기 이동시키기

크게는 요 두 가지밖에 없지만, 확산되서 더해질 먼지와 기존의 먼지를 별개로 구분해야했기에 이 부분이 조금 귀찮았다.
그래서 확산시킬 먼지는 Queue에 담고, Queue에서 먼지 정보를 꺼내가면서 확산된 먼지의 정보를 2차원 배열에 담아주었다. 이를 반복하면 됨

	// 미세먼지 확산
	private static void diffusion() {
		int[][] move = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
		while (!q.isEmpty()) {
			Point p = q.poll();
			if (p.dust <= 0)
				continue;
			// 얼마나 이동할 수 있는지
			int cnt = 0;
			int amount = p.dust / 5; // 확산되는 미세먼지의 양
			for (int j = 0; j < 4; j++) {
				int ni = p.i + move[j][0];
				int nj = p.j + move[j][1];

				if (ni < 0 || nj < 0 || ni >= r || nj >= c || map[ni][nj] == -1)
					continue;

				cnt++;
				map[ni][nj] += amount;
			}
			map[p.i][p.j] += (p.dust - amount * cnt);
		}
		flow(cleaner); // 확산 완료 후 공기 이동
		add(); // 계산을 위해 큐 및 배열 초기화
	}

 

공기 이동은 그냥 인덱스를 잘 계산해서 옮겨주면 된다.

 

<전체 소스코드>

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

public class Main {

	private static int r, c, t, cleaner;
	private static int[][] map;
	private static Queue<Point> q;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = parse(st.nextToken()); // 세로
		c = parse(st.nextToken()); // 가로
		t = parse(st.nextToken()); // 단위시간
		map = new int[r][c];
		q = new LinkedList<>();
		cleaner = 0;
		for (int i = 0; i < r; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < c; j++) {
				map[i][j] = parse(st.nextToken());
				if (map[i][j] == -1)
					cleaner = i;
			}
		} // end Input
		add();

		while (t-- > 0)
			diffusion(); // 미세먼지 확산
		System.out.println(getDust());
	}

	// 유효한 칸을 큐에 담아줌
	private static void add() {
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (map[i][j] > 0) {
					q.offer(new Point(i, j, map[i][j]));
					map[i][j] = 0;
				}
			}
		}
	}

	// 미세먼지 확산
	private static void diffusion() {
		int[][] move = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
		while (!q.isEmpty()) {
			Point p = q.poll();
			if (p.dust <= 0)
				continue;
			// 얼마나 이동할 수 있는지
			int cnt = 0;
			int amount = p.dust / 5; // 확산되는 미세먼지의 양
			for (int j = 0; j < 4; j++) {
				int ni = p.i + move[j][0];
				int nj = p.j + move[j][1];

				if (ni < 0 || nj < 0 || ni >= r || nj >= c || map[ni][nj] == -1)
					continue;

				cnt++;
				map[ni][nj] += amount;
			}
			map[p.i][p.j] += (p.dust - amount * cnt);
		}
		flow(cleaner); // 확산 완료 후 공기 이동
		add(); // 계산을 위해 큐 및 배열 초기화
	}

	// 공기 이동
	private static void flow(int cleaner) {
		// 아래 순환 사이클
		for (int i = cleaner + 1; i < r - 1; i++) // 위
			map[i][0] = map[i + 1][0];
		for (int j = 0; j < c - 1; j++) // 왼쪽
			map[r - 1][j] = map[r - 1][j + 1];
		for (int i = r - 1; i > cleaner; i--) // 아래
			map[i][c - 1] = map[i - 1][c - 1];
		for (int j = c - 1; j > 1; j--) // 오른쪽
			map[cleaner][j] = map[cleaner][j - 1];
		map[cleaner][1] = 0;

		// 위쪽 순환 사이클
		cleaner--;
		for (int i = cleaner - 1; i > 0; i--) // 아래
			map[i][0] = map[i - 1][0];
		for (int j = 0; j < c - 1; j++) // 왼쪽
			map[0][j] = map[0][j + 1];
		for (int i = 0; i < cleaner; i++) // 위
			map[i][c - 1] = map[i + 1][c - 1];
		for (int j = c - 1; j > 1; j--) // 오른쪽
			map[cleaner][j] = map[cleaner][j - 1];
		map[cleaner][1] = 0;
	}

	// 먼지 양 구하기
	private static int getDust() {
		int sum = 0;
		while (!q.isEmpty())
			sum += q.poll().dust;
		return sum;
	}

	static class Point {
		int i, j, dust;

		Point(int i, int j, int dust) {
			this.i = i;
			this.j = j;
			this.dust = dust;
		}

	}

	private static int parse(String s) {
		return Integer.parseInt(s);
	}
}