[JAVA] BOJ 백준 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초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

전체 코드

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

public class Main {
	static int R;
	static int C;
	static int[][] home;
	static int cx;
	static int cy;
	
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        home = new int[R][C];
        for(int i=0; i<R; i++) {
        	st = new StringTokenizer(bf.readLine(), " ");
        	for(int j=0; j<C; j++) {
        		home[i][j] = Integer.parseInt(st.nextToken());
        		if(home[i][j] == -1) { cx = i; cy = j;}
        	}
        }
        for(int t=0; t<T; t++) {
        	spread();
        }
        int result = 0;
        for(int i=0; i<R; i++)
        	for(int j=0; j<C; j++)
        		result += home[i][j];
        sb.append(result+2);
        System.out.println(sb.toString());
        
    }
    static void spread() {
    	int[] dx = {-1, 0, 1, 0};
    	int[] dy = {0, 1, 0, -1};
    	int nx, ny, count;
    	int[][] add = new int[R][C];
    	// 확산
    	for(int i=0; i<R; i++) {
    		for(int j=0; j<C; j++) {
    			count = 0;
    			for(int d=0; d<4; d++) {
    				nx = i+dx[d];
    				ny = j+dy[d];
    				if(nx < 0 || ny < 0 || nx >= R || ny >= C || home[nx][ny] == -1) continue;
    				count ++; add[nx][ny] += home[i][j] / 5;
    			}
				add[i][j] -= (home[i][j] / 5) * count;
    		}
    	}
    	for(int i=0; i<R; i++)
    		for(int j=0; j<C; j++)
    			home[i][j] += add[i][j];
    	
    	// 공청
    	// 1. 윗 부분
    	nx = 0;
    	ny = 0;
    	int idx = 0;
    	int x = cx-2; int y = cy;
    	while(x != cx-1 || y != cy) {
    		nx = x+dx[idx]; ny = y+dy[idx];
    		if(nx < 0 || ny < 0 || nx >= cx || ny >= C) {
    			idx +=1;
    			if(idx > 3) idx = 0;
    			nx = x+dx[idx]; ny = y+dy[idx];
    		}
    		if(home[nx][ny] != -1)
    			home[x][y] = home[nx][ny];
    		else home[x][y] =0;
    		x = nx; y = ny;
    	}
    	// 2. 아랫 부분
    	x = cx+1; y = cy;
    	while(x != cx || y != cy) {
    		nx = x+dx[idx]; ny = y+dy[idx];
    		if(nx < cx || ny < 0 || nx >= R || ny >= C) {
    			idx -=1;
    			if(idx < 0) idx = 3;
    			nx = x+dx[idx]; ny = y+dy[idx];
    		}
    		if(home[nx][ny] != -1)
    			home[x][y] = home[nx][ny];
    		else home[x][y] =0;
    		x = nx; y = ny;
    	}   	
    }
}

한 줄 씩 살펴보자!

static int R;
static int C;
static int[][] home;
static int cx;
static int cy;

R, C, home에 입력 받은 배열을 저장해준다.

cx, cy는 공기 청정기의 위치이다. (공기청정기의 두 칸은 붙어있으므로 아래칸의 값만 저장해주었다.)

static void spread() {
	int[] dx = {-1, 0, 1, 0};
	int[] dy = {0, 1, 0, -1};
	int nx, ny, count;
	int[][] add = new int[R][C];
	// 확산
	for(int i=0; i<R; i++) {
		for(int j=0; j<C; j++) {
			count = 0;
			for(int d=0; d<4; d++) {
				nx = i+dx[d];
				ny = j+dy[d];
				if(nx < 0 || ny < 0 || nx >= R || ny >= C || home[nx][ny] == -1) continue;
				count ++; add[nx][ny] += home[i][j] / 5;
			}
		add[i][j] -= (home[i][j] / 5) * count;
		}
	} 	for(int i=0; i<R; i++)
    		for(int j=0; j<C; j++)
    			home[i][j] += add[i][j];

먼저 미세먼지가 확산하게 된다. 미세먼지가 있는 모든 칸에서 “동시에” 일어난다. 이때 4방을 탐색하여 미세먼지가 이동할 수 있는 칸이면(격자를 벗어나거나, 공기청정기가 있는 경우 제외) 현 위치의 미세먼지를 5로 나눈 값만큼 이동하게 된다.

그러므로 우리는 하나의 격자에서 4방향을 탐색하여 미세먼지를 이동시켜야 한다.

미세먼지가 이동하는 양은 add 배열에 담아서 모든 격자에서 조사가 끝난 후 더해주겠다.(동시에 일어나는 과정이기 때문에 미리 home 배열에 넣어주면 다음 칸에서는 이동한 미세먼지까지 고려하게 된다.

nx = 0;
ny = 0;
int idx = 0;
int x = cx-2; int y = cy;
while(x != cx-1 || y != cy) {
	nx = x+dx[idx]; ny = y+dy[idx];
	if(nx < 0 || ny < 0 || nx >= cx || ny >= C) {
		idx +=1;
		if(idx > 3) idx = 0;
		nx = x+dx[idx]; ny = y+dy[idx];
	}
	if(home[nx][ny] != -1)
		home[x][y] = home[nx][ny];
	else home[x][y] =0;
	x = nx; y = ny;
}

공기청정기 위쪽은 → , ^, <-, V 방향으로 이동하게 된다. 하지만 그 방향으로 움직이게 되면 값을 옮기는데 힘들어진다. 그렇기 때문에 반대로 이동방향을 잡아서 값을 넘겨가는 형태로 구현하겠다.

첫번째로 윗부분 공기청정기의 이동을 진행한다. x, y에 윗부분의 공기청정기 위칸의 값을 넣어준다. 이동이 전부 끝나면 공기청정기로 돌아오기 때문에 while문은 그때까지만 진행하는 걸로 하자

반대 방향으로 탐색을 시작하므로 idx는 0부터 3으로 가게 된다. 격자를 벗어나는 경우 그 방향으로 이동이 불가능한 경우기 때문에 회전을 바꿔서 다음 진행할 곳을 수정해준다. 그 값이 -1이 아니면(공기청정기) 다음 이동 방향의 미세먼지의 양을 복사해준다. 다음 진행할 곳이 미세먼지인 경우는 미세먼지로부터 정화된 곳이기 때문에 0으로 수정해준다.

    	x = cx+1; y = cy;
    	while(x != cx || y != cy) {
    		nx = x+dx[idx]; ny = y+dy[idx];
    		if(nx < cx || ny < 0 || nx >= R || ny >= C) {
    			idx -=1;
    			if(idx < 0) idx = 3;
    			nx = x+dx[idx]; ny = y+dy[idx];
    		}
    		if(home[nx][ny] != -1)
    			home[x][y] = home[nx][ny];
    		else home[x][y] =0;
    		x = nx; y = ny;
    	}   	
    }
}

아랫부분의 탐색은 윗부분의 탐색과 다르지 않다, idx가 3에서 0으로 가는 것만 유의하면 된다.