백준 17144 - 미세먼지 안녕!

Java

17144 번 - 미세먼지 안녕!

문제

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

접근 방법

t초 만큼의 반복한다.

queue에 미세먼지의 위치들을 다 넣어놓은 다음, 미세먼지 하나씩 꺼내여 4방향으로 퍼뜨린다.

퍼뜨릴 때 주의할 점이 퍼뜨린 값을 다른 칸에 미리 넣어 버리면, 다음 미세먼지가 퍼뜨릴 때 영향이 있으므로, 퍼뜨린 값만 저장하는 2차원 배열(spread)을 설정해 그 곳에 퍼뜨린 값들을 저장한다.

미세먼지들을 다 퍼뜨렸으면, 기존의 미세먼지의 2차원 배열(map)과 퍼뜨린 값들을 저장한 2차원 배열(spread)들을 합친다.

이제 위 쪽 공기청정기와 아래 쪽 공기청정기에서 순환되는 부분을 옮긴다.

옮긴 이후, 2차원 배열을 전부 탐색하여 미세먼지 값이 5 이상인 미세먼지 칸을 다음에 퍼뜨릴 미세먼지로 queue에 넣는다.

코드

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

public class Main {
	static int n, m, t, result, fU, fD;
	static int[][] map;
	static int[][] spread;
	
	// 상하좌우 탐색
	static int dy[] = {-1,1,0,0};
	static int dx[] = {0,0,-1,1};
	// 시계 방향 인덱스
	static int s1y[] = {-1,0,1,0};
	static int s1x[] = {0,1,0,-1};
	// 반 시계 방향 인덱스
	static int s2y[] = {1,0,-1,0};
	static int s2x[] = {0,1,0,-1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	t = stoi(stk.nextToken());
    	
    	map = new int[n][m];
    	spread = new int[n][m];
    	
    	Queue<int[]> dirt = new LinkedList<int[]>();
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++) {
    			map[i][j] = stoi(stk.nextToken());
    			if(map[i][j] != 0 && map[i][j] != -1)
    				dirt.add(new int[] {i,j});
    			if(map[i][j] == -1)
    				fD = i;
    		}
    	}
    	fD += 1;			// 공기 청정기 위 쪽의 위치 (y값)
    	fU = fD - 3;		// 공기 청정기 아래 쪽의 위치 (y값)
    	
    	int size = 0, cal, cnt = 0, y, x, ny, nx, dir;
    	int[] temp;
    	while(t-- > 0) {
    		// 미세먼지 확산
    		size = dirt.size();
    		
    		while(size-- > 0) {
    			temp = dirt.poll();
    			y = temp[0];
    			x = temp[1];
    			cal = map[y][x] / 5;			// 확산되는 미세먼지의 양
    			for(int i = 0; i < 4; i++) {	// 미세먼지 한 곳에서 4방향으로 퍼뜨린다
    				ny = y + dy[i];
    				nx = x + dx[i];
    				
    				if(isIn(ny,nx) && map[ny][nx] != -1) {
    					spread[ny][nx] += cal;
    					cnt++;
    				}
    			}
    			map[y][x] -= cal * cnt;
    			cnt = 0;
    		}
    		
    		// 퍼진 미세먼지들을 합친다.
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < m; j++) {
    				map[i][j] += spread[i][j];
    				spread[i][j] = 0;
    			}
    		}
    		
    		// 미세먼지 흡수 - 위쪽
    		y = fU;
    		x = 0;
    		dir = 0;
    		while(true) {
    			y += s1y[dir];
    			x += s1x[dir];
    			// 범위를 벗어나면 방향을 바꾼다.
    			if(y < 0 || y >= fU + 2 || x < 0 || x >= m) {
    				y -= s1y[dir];
        			x -= s1x[dir];
        			dir++;
        			y += s1y[dir];
        			x += s1x[dir];
    			}
    			if(map[y][x] == -1) {
    				map[y - s1y[dir]][x - s1x[dir]] = 0;
    				break;
    			}
    			
    			map[y - s1y[dir]][x - s1x[dir]] = map[y][x];
    		}
    		
    		// 미세먼지 흡수 - 아래쪽
    		y = fD;
    		x = 0;
    		dir = 0;
    		while(true) {
    			y += s2y[dir];
    			x += s2x[dir];
    			// 범위를 벗어나면 방향을 바꾼다.
    			if(y <= fD - 2 || y >= n || x < 0 || x >= m) {
    				y -= s2y[dir];
        			x -= s2x[dir];
        			dir++;
        			y += s2y[dir];
        			x += s2x[dir];
    			}
    			if(map[y][x] == -1) {
    				map[y - s2y[dir]][x - s2x[dir]] = 0;
    				break;
    			}
    			
    			map[y - s2y[dir]][x - s2x[dir]] = map[y][x];
    		}
    		
    		// 다음 퍼뜨릴 미세먼지를 기록한다.
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < m; j++) {
    				if(map[i][j] >= 5)		// 5 미만의 미세먼지 크기면 확산되지 않음
    					dirt.add(new int[] {i,j});
    			}
    		}
    	}

		// t초 이후 방 안의 모든 미세먼지의 합
    	for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(map[i][j] != -1)
					result += map[i][j];
			}
    	}
    	
    	System.out.println(result);
    	br.close();
	}

	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= m)
            return false;
        return true;
    }
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

미세먼지들을 순환 시키기 전, 그 위치를 저장해 놓아 제대로 퍼뜨리지 못하는 실수를 하였다.

개선할 점

없습니다.