✔문제링크

BOJ17144. 미세먼지 안녕

📝문제설명

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

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

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

• (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
• 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
• 확산되는 양은 Ar,c/5이고 소수점은 버린다.
• (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.

2. 공기청정기가 작동한다.

• 공기청정기에서는 바람이 나온다.
• 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
• 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
• 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

💡해결방법

먼저, 미세먼지의 확산 동작을 수행할 func()라는 함수를 만들었다.
이 함수는 미세먼지 분포를 저장할 2차원 배열 map을 순회하며, 미세먼지가 존재를 확인하고 해당 좌표의 4방향으로 확산하는 연산을 수행한다.

이때, 미세먼지의 확산은 동시에 일어나므로 이 동작이 서로에게 영향을 미치지 않도록 tmp라는 2차원 임시배열을 이용하였다.

다음으로는 공기청정기의 바람 순회를 위한 work() 함수이다.

// 윗쪽 공기청정기 순환을 위한 델타값
	int[] dr = { -1, 0 , 1, 0};
	int[] dc = { 0, 1, 0, -1};
	int k=0 , x = loc[0][0], y = loc[0][1];
	while(true) {
		if(k >= 4) break;
		int xx = x+dr[k];
		int yy = y+dc[k];
		if(xx<0 || xx>=loc[0][0]+1 || yy<0 || yy>=C) {
			k++;
			continue;
		}
		map[x][y] = map[xx][yy];
		x=xx;
		y=yy;
	}
	map[loc[0][0]][loc[0][1]] = -1;
	map[loc[0][0]][loc[0][1]+1] = 0;

다음과 같이 공기 순회의 반대방향으로 그래프를 순회하며 값을 한 칸씩 당기는 연산을 진행한다. 연산을 끝마치면, 공기청정기의 위치와 공기청정기에서 바람 나오는 위치의 값을 알맞게 초기화 한다.

👍코드

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class BOJ17144 {

	static int R, C, T, ANS;
	static int[] dx = { 0, 1, 0, -1};
	static int[] dy = { 1, 0, -1, 0};
	static int[][] map, loc;
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src/input17144.txt"));
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();
		T = sc.nextInt();
		map = new int[R][C];
		loc = new int[2][2];
		int a = 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) {
					loc[a][0] = i;
					loc[a][1] = j;
					a++;
				}
			}
		}
		
		for(int i=0; i<T; i++) {
			func();
			work();
		}
		
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				if(map[i][j] > 0) ANS += map[i][j];
			}
		}
		System.out.println(ANS);
		
	}
	/** 
	 * work() : 공기청정기 동작을 구현하기 위한 함수
	 * 공기청정기를 위아래로 나누어 공기청정기 순환방향으로 미세먼지를 한칸씩 이동시킨다.
	 **/
	private static void work() {
		// 윗쪽 공기청정기 순환을 위한 델타값
		int[] dr = { -1, 0 , 1, 0};
		int[] dc = { 0, 1, 0, -1};
		int k=0 , x = loc[0][0], y = loc[0][1];
		while(true) {
			if(k >= 4) break;
			int xx = x+dr[k];
			int yy = y+dc[k];
			if(xx<0 || xx>=loc[0][0]+1 || yy<0 || yy>=C) {
				k++;
				continue;
			}
			map[x][y] = map[xx][yy];
			x=xx;
			y=yy;
		}
		map[loc[0][0]][loc[0][1]] = -1;
		map[loc[0][0]][loc[0][1]+1] = 0;
		
		
		// 아랫쪽 공기청정기 순환을 위한 델타값
		dr = new int[] { 1, 0, -1, 0};
		dc = new int[] { 0, 1, 0, -1};
		k =0;
		x = loc[1][0];
		y = loc[1][1];
		while(true) {
			if(k >= 4) break;
			int xx = x+dr[k];
			int yy = y+dc[k];
			if(xx<loc[1][0] || xx>=R || yy<0 || yy>=C) {
				k++;
				continue;
			}
			map[x][y] = map[xx][yy];
			x=xx;
			y=yy;
		}
		map[loc[1][0]][loc[1][1]] = -1;
		map[loc[1][0]][loc[1][1]+1] = 0;
	}
	/**
	 * func() : 미세먼지의 확산을 구현한 함수
	 * (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
	 * 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
	 * 확산되는 양은 Ar,c/5이고 소수점은 버린다
	 * (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
	 */
	private static void func() {
		int[][] tmp = new int[R][C];
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				if(map[i][j] > 0) {
					int val = map[i][j]/ 5;
					int cnt = 0;
					for(int k=0; k<4; k++) {
						int xx = i+dx[k];
						int yy = j+dy[k];
						if(xx<0 || xx>=R || yy<0 || yy>=C) continue;
						////공기청정기 위치인지 확인 
						if(xx == loc[0][0] && yy == loc[0][1]) continue;
						if(xx == loc[1][0] && yy == loc[1][1]) continue;
						
						tmp[xx][yy]+=val;
						cnt++;
					}
					map[i][j] -= val*cnt;
				}
			}
		}
		
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				map[i][j] += tmp[i][j];
			}
		}
	}
}