[17144] 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

---

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

class Main {

	static int R, C, T;
	static int[][] map;
	static Queue<Pair> queue;
	static int[][] dir = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
	static ArrayList<Pair> air = new ArrayList<Pair>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		R = sc.nextInt();
		C = sc.nextInt();
		T = sc.nextInt();
		map = new int[R][C];
		queue = new LinkedList<Pair>();

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				map[i][j] = sc.nextInt();
				if (map[i][j] != -1 && map[i][j] != 0)
					queue.offer(new Pair(i, j, map[i][j]));
				if (map[i][j] == -1) {
					air.add(new Pair(i, j, map[i][j]));
				}
			}
		}

		for (int i = 0; i < T; i++) {
			spread();
			wind();

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

	}
	
	
	
	public static void wind() {
		Pair p1 = air.get(0);
		Pair p2 = air.get(1);
		
		// 반시계방향 순환
		// 1. 위에서 아래로
		for(int i=p1.x-1; i>0; i--) {
			map[i][0] = map[i-1][0];
		}
		// 2. 오른쪽에서 왼쪽으로
		for(int i=0; i<C-1; i++) {
			map[0][i] = map[0][i+1];
		}
		// 3. 아래서 위로
		for(int i=0; i<p1.x; i++) {
			map[i][C-1] = map[i+1][C-1];
		}
		// 4. 왼쪽에서 오른쪽으로
		for(int i=C-1; i>p1.y+1; i--) {
			map[p1.x][i] = map[p1.x][i-1];
		}
		map[p1.x][p1.y+1] = 0;
		
		// 시계방향 순환
		// 1. 아래에서 위로
		for(int i=p2.x+1; i<R-1; i++) {
			map[i][0] = map[i+1][0]; 
		}
		// 2. 오른쪽에서 왼쪽으로
		for(int i=0; i<C-1; i++) {
			map[R-1][i] = map[R-1][i+1];
		}
		// 3. 위에서 아래로
		for(int i=R-1; i>p2.x; i--) {
			map[i][C-1] = map[i-1][C-1];
		}
		// 4. 왼쪽에서 오른쪽으로
		for(int i=C-1; i>p2.y+1; i--) {
			map[p2.x][i] = map[p2.x][i-1];
		}
		map[p2.x][p2.y+1] = 0;
	}

	public static void spread() {

		while (!queue.isEmpty()) {
			Pair p = queue.poll();
			int dust = p.value / 5;

			int cnt = 0;

			for (int i = 0; i < 4; i++) {
				int nx = p.x + dir[i][0];
				int ny = p.y + dir[i][1];

				if (isInside(nx, ny) && map[nx][ny] != -1) {
					map[nx][ny] += dust;
					cnt++;
				}
			}
			map[p.x][p.y] -= (dust * cnt);
			
		}
	}

	public static boolean isInside(int x, int y) {
		if (x >= 0 && y >= 0 && x < R && y < C)
			return true;
		else
			return false;
	}

	public static void print() {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
}

class Pair {
	int x;
	int y;
	int value; 
	
	Pair(int x, int y, int value) {
		this.x = x;
		this.y = y;
		this.value = value;
	}
}

---

2019 상반기 SW 역량테스트 기출 문제 입니다.  먼저 2차원 배열에 있는 미세먼지가 확산되고, 1열에 크기 2짜리 있는 공기청정기가 위쪽은 반시계방향으로 순환하고, 아래쪽은 시계방향으로 순환시켜 T초 후에 남아있는 미세먼지 양을 추력하는 문제입니다.

그래서 저는 먼저 순차적으로 미세먼지를 BFS를 사용해서 각 미세먼지를 상하좌우로 확산시켰습니다. 그리고 이제 공기청정기를 사용하여 반시계 방향으로 순환시키는 경우 공기청정기 부터 오른쪽으로 먼저 하게 되면 끝에 있는 먼지를 계속 저장해주고 저장된 먼지를 다시 처음에 넣어주고 복잡해졌습니다. 그래서 해결한 방법은 공기청정기에 들어가는 먼지를 먼저 없애는 것이었습니다. 반시계, 시계 방향 모두 공기청정기가 있는 방향으로 먼지를 먼저 내리거나 올려서 없애면 마지막에 있는 미세먼지는 따로 저장할 필요없이 순환시킬 수 있었습니다. 또한 먼지를 순환시킬 때 방향이 모두 달라서 반복문에서 i의 시작점과 끝점을 확실하게 설정하는 것이 헷갈리고 어려웠습니다.

[ 문제 풀이 ]

1. 입력받을 때 미세먼지가 있는 좌표를 Queue에 넣어서 BFS를 하게 했습니다. 좌표가 -1이라면 공기청정기가 있는 자리이므로 좌표를 air 라는 ArrayList에 저장했습니다. 공기청정기의 크기는 항상 2이기 때문에 꼭 ArrayList로 하지 않고 크기 2인 배열에 해도 상관없습니다.

2. 이제 T 초 만큼 반복문을 돌면서 spread() 라는 함수로 미세먼지를 먼저 퍼뜨리고, wind() 라는 함수로 미세먼지를 순환시킵니다.

2-1. spread() 함수는 미세먼지가 있는 좌표를 Queue에 넣어서 BFS하는 함수입니다.

2-2. wind() 함수는 미세먼지가 퍼져있는 지도에서 미세먼지를 순환시키는 함수입니다. 반시계방향 4개, 시계방향 4개 총 8개의 반복문이 사용됩니다.

3. 반복문이 한번 반복될 때 마다 마지막에 미세먼지의 좌표를 다시 Queue에 넣어줘서 다음번 확산을 준비합니다.

4. 마지막에 미세먼지를 모두 answer에 더해서 출력합니다.