boj 17144 미세먼지 안녕!

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

1초 동안 다음과 같은 일이 일어납니다.

1. 미세먼지가 확산되며 미세먼지가 있는 모든 칸에서 동시에 일어납니다.

 - 인접한 4방향으로 확산됩니다.

 - 인접한 방향이 맵 밖이거나 공기청정기가 있는 곳이라면 확산이 일어나지 않습니다.

 - 확산되는 양은 list[i][j] / 5입니다. (소수점 버림)

 - (i, j)에 남은 미세먼지 양은 list[i][j] - (list[i][j] / 5) * (확산된 방향의 갯수)입니다.

2. 공기청정기가 작동됩니다.

 - 위쪽 공기청정기의 바람은 반시계방향으로 순환, 아래쪽 공기청정기의 바람은 시계방향으로 순환합니다.

 - 미세먼지가 바람의 방향대로 한 칸씩 이동합니다.

 - 공기청정기로 들어가는 미세먼지는 정화됩니다.

 

위의 모든것을 직접 구현해야합니다.

 

우선 2중for문을 돌면서 미세먼지를 확산시킵니다. 이 때 확산이 동시에 일어나야하므로 nextlist라는 변수를 사용하였습니다.

그 다음 공기청정기를 작동시켜 위쪽에는 반시계방향으로, 아래쪽에는 시계방향으로 값을 회전시켜줍니다.

이 과정을 T번 반복하여 T초 후 남아있는 미세먼지 양을 출력합니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[51][51];
    static int nextlist[][] = new int[51][51];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int cleaner[][] = new int[2][2];
    static int N, M, T;
 
    static void clear() {
        int x = cleaner[0][0];
        int y = cleaner[0][1];
 
        x--;
        int d = 3;
        while (true) {
            int nx = x + direct[d][0];
            int ny = y + direct[d][1];
 
            if (nx <= 0 || ny <= 0 || nx > cleaner[0][0] || ny > M) {
                d = (d + 1) % 4;
                continue;
            }
            list[x][y] = 0;
            if (list[nx][ny] == -1)
                break;
 
            list[x][y] = list[nx][ny];
            x = nx;
            y = ny;
        }
 
        x = cleaner[1][0];
        y = cleaner[1][1];
 
        x++;
        d = 1;
        while (true) {
            int nx = x + direct[d][0];
            int ny = y + direct[d][1];
 
            if (nx < cleaner[1][0] || ny <= 0 || nx > N || ny > M) {
                d = (d + 3) % 4;
                continue;
            }
            list[x][y] = 0;
            if (list[nx][ny] == -1)
                break;
 
            list[x][y] = list[nx][ny];
            x = nx;
            y = ny;
        }
    }
    
    static void spread() {
        for (int i = 1; i <= N; i++)
            Arrays.fill(nextlist[i], 0);
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j] > 0) {
                    int diff = list[i][j] / 5;
                    int cnt = 0;
                    for (int d = 0; d < 4; d++) {
                        int nx = i + direct[d][0];
                        int ny = j + direct[d][1];
 
                        if (nx <= 0 || ny <= 0 || nx > N || ny > M)
                            continue;
                        if (list[nx][ny] == -1)
                            continue;
 
                        nextlist[nx][ny] += diff;
                        cnt++;
                    }
 
                    nextlist[i][j] += (list[i][j] - diff * cnt);
                }
            }
        }
        
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j] == -1)
                    continue;
                list[i][j] = nextlist[i][j];
            }
        }
    }
 
    static void func() {
        for (int t = 1; t <= T; t++) {
            spread();
            clear();
        }
    }
 
    static void print() {
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j] > 0)
                    ans += list[i][j];
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int t = 0;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
                if (list[i][j] == -1) {
                    cleaner[t][0] = i;
                    cleaner[t++][1] = j;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}