[Boj] G5 17144 미세먼지 안녕!

---

 

17144. 미세먼지 안녕!

 

 

---

 

 

 

문제 링크

 

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

 

 

 

---

 

 

 

 

 

작년에 알고리즘 공부 하나도 안했을 때, 제대로 풀지도 못했던 문제였는데 35분만에 풀었다.

 

물론 아직 갈 길이 멀지만 이 정도 수준의 문제는 쉽게 풀 수 있을만큼 성장한 것 같다.

 

더 노력해야지 :)

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Boj_G5_17144_미세먼지안녕 {
    static int R, C, T, upper, lower;
    static int[][] map;
    static int[] dx = { 0, -1, 0, 1 };
    static int[] dy = { -1, 0, 1, 0 };
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken()); // I
        C = Integer.parseInt(st.nextToken()); // J
        T = Integer.parseInt(st.nextToken()); // 시간
        map = new int[R + 1][C + 1];
 
        for (int i = 1; i <= R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= C; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == -1 && upper == 0) { // 청정기 윗부분, 아랫부분 구하기
                    upper = i;
                    lower = i + 1;
                }
            }
        }
        for (int time = 0; time < T; time++) {
            spread();
            circulate();
        }
        System.out.println(getDust());
 
    }
 
    private static int getDust() {
        int dust = 0;
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                if(map[i][j] > 0)
                    dust += map[i][j];
            }
        }
        return dust;
    }
 
    private static void circulate() {
        // 2 공기청정기 작동
        // 위쪽은 반시계방향 순환
        // 아래쪽은 시계방향 순환
        // 미세먼지 바람의 방향대로 한칸씩 이동
        // 미세먼지로 들어가는 먼지는 정화됨
 
        // 위쪽 반시계
        for (int i = upper - 1; i > 1; i--)
            map[i][1] = map[i - 1][1];
 
        for (int j = 1; j < C; j++)
            map[1][j] = map[1][j + 1];
 
        for (int i = 1; i < upper; i++)
            map[i][C] = map[i + 1][C];
 
        for (int j = C; j > 2; j--)
            map[upper][j] = map[upper][j - 1];
 
        map[upper][2] = 0;
 
        // 아래쪽 시계
        for (int i = lower + 1; i < R; i++)
            map[i][1] = map[i + 1][1];
 
        for (int j = 1; j < C; j++)
            map[R][j] = map[R][j + 1];
 
        for (int i = R; i > lower; i--)
            map[i][C] = map[i - 1][C];
 
        for (int j = C; j > 2; j--)
            map[lower][j] = map[lower][j - 1];
 
        map[lower][2] = 0;
 
    }
 
    private static void spread() {
        // 1 확산
        // 미세먼지 네 방향으로 확산
        // 공기청정기가 있거나, 칸이 없으면 확산 X
        // 확산되는 양은 map[r][c] / 5, 소수점 버림
        // 남는 양은 map[r][c] - ( map[r][c] / 5 ) * 확산된 방향 수
        
        int[][] temp = new int[R + 1][C + 1];
 
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                // 먼지가 있다면
                if (map[i][j] > 0) {
 
                    int count = 0; // 확산 몇번?
                    // 네 방향 확산
                    for (int d = 0; d < 4; d++) {
                        int ny = i + dy[d];
                        int nx = j + dx[d];
 
                        // 공기 청정기가 없거나 , 칸이 있으면 확산
                        if (isRange(ny, nx) && map[ny][nx] != -1) {
                            temp[ny][nx] += map[i][j] / 5;
                            count++;
                        }
                    }
                    map[i][j] -= (map[i][j] / 5) * count;
                }
            }
        }
 
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                if (temp[i][j] > 0) {
                    map[i][j] += temp[i][j];
                }
            }
        }
 
    }
 
    private static boolean isRange(int ny, int nx) {
        return ny >= 1 && nx >= 1 && ny <= R && nx <= C;
    }
 
}