[Java] 17144번 : 미세먼지 안녕!

문제 풀이 해당 문제는 시뮬레이션 / 구현 문제로 확산되는 미세먼지와 이를 빨아드리는 공기청정기로 변화하는 공기 질을 구하는 문제이다.

문제는 복잡해 보이지만 단계를 나누어 구현하고 이를 합치면 간단하게 풀 수 있다.

1. 미세먼지 확산 구현 가장 먼저 미세먼지가 확산 되는 것을 구현했다. 해당 구현은 입력을 받을 때 미세먼지의 위치를 저장한다. 이 후 저장된 미세먼지를 모두 불러와 주변에 확산시키고 이를 대기에 저장한다.

이 때 확산은 동시에 일어나는 것이므로 먼저 계산한 확산된 먼지가 이후 확산되기 전의 먼지에 관여하면 안된다. 그렇기에 tempBoard에 저장하고 모든 사이클이 끝나면 이를 연산해주는 방식으로 구현했다. 이를 주어진 횟수만큼 반복해주었다.

public static Queue<Air> dirty = new LinkedList<>();

...

while(T-->0) {
    Queue<Air> qu = new LinkedList<>();
    int[][] visited = new int[R][C];
    tempBoard = new int[R][C];

    while(!dirty.isEmpty()) {
        qu.add(dirty.poll());
    }

    while(!qu.isEmpty()) {
        Air cur = qu.poll();

        if(visited[cur.y][cur.x]>0)continue;

        int count = 0;
        int spread = (int) Math.floor(cur.size / 5);
        for(int i = 0; i < 4; i++) {
            int mx = cur.x + dx[i];
            int my = cur.y + dy[i];

            if(mx < 0 || mx >= C || my <0 || my >= R || board[my][mx] == -1 )continue;
            count++;
            tempBoard[my][mx] += spread;

        }
        tempBoard[cur.y][cur.x] -= spread * count;
    }

    for(int i = 0 ; i < R; i++) {
        for(int j = 0 ; j < C;j++) {
            board[i][j] += tempBoard[i][j];
        }
    }

    for(int i = 0 ; i < R; i++) {
        for(int j = 0 ; j < C;j++) {
            if(board[i][j] > 0) dirty.add(new Air(j,i,board[i][j]));
        }
    }

}

  ...

2. 공기 순환 구현 다음으로는 공기 순환을 구현하였다. 이는 입력 받은 공기청정기를 기준으로 시계 / 반시계 방향으로 순환하는데, 이 때 반복문을 이용하면 간단하게 구현할 수 있다.

public static void cleaningTopAir() {
    for(int i = airU[0] - 1; i > 0; i--) {
        board[i][0] = board[i-1][0];
    }

    for(int i =0; i < C-1; i++) {
        board[0][i] = board[0][i+1];
    }

    for(int i = 0; i < airU[0] ; i++) {
        board[i][C-1] = board[i+1][C-1];
    }

    for(int i = C-1; i > 1; i--) {
        board[airU[0]][i] = board[airU[0]][i-1];
    }
    board[airU[0]][1] = 0;
}
public static void cleaningBottomAir() {
    for(int i = airD[0] + 1; i < R - 1; i++) {
        board[i][0] = board[i+1][0];
    }

    for(int i =0; i < C-1; i++) {
        board[R-1][i] = board[R-1][i+1];
    }

    for(int i = R-1; i > airD[0] ; i--) {
        board[i][C-1] = board[i-1][C-1];
    }

    for(int i = C-1; i > 1; i--) {
        board[airD[0]][i] = board[airD[0]][i-1];
    }
    board[airD[0]][1] = 0;
}

3. 두 과정 합치기 위에서 구현한 두 과정을 하나의 반복문 안에 구현하면 문제를 풀 수 있다.

풀이 코드

import java.util.*;
import java.io.*;
public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static int INF = 100_000_000;
    public static int[] dx = {0,1,0,-1};
    public static int[] dy = {-1,0,1,0};

    public static int R;
    public static int C;
    public static int T;
    public static int[][] board;
    public static int[][] tempBoard;
    public static int[] airU = new int[2];
    public static int[] airD = new int[2];
    public static Queue<Air> dirty = new LinkedList<>();

    public static class Air{
        int x;
        int y;
        int size;

        public Air() {}
        public Air(int x, int y, int size) {
            this.x = x;
            this.y = y;
            this.size = size;
        }
    }

    public static void main(String[] args) throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        board = new int[R][C];

        boolean isFind = false;
        for(int i = 0 ; i < R; i++) {
            board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for(int x = 0; x < C; x++){
                if(board[i][x] == -1 && !isFind) {
                    airU[0] = i;
                    airD[0] = i+1;
                    isFind =true;
                }
                else if(board[i][x] > 0) {
                    dirty.add(new Air(x,i,board[i][x]));
                }
            }
        }

        while(T-->0) {
            Queue<Air> qu = new LinkedList<>();
            int[][] visited = new int[R][C];
            tempBoard = new int[R][C];

            while(!dirty.isEmpty()) {
                qu.add(dirty.poll());
            }

            while(!qu.isEmpty()) {
                Air cur = qu.poll();

                if(visited[cur.y][cur.x]>0)continue;

                int count = 0;
                int spread = (int) Math.floor(cur.size / 5);
                for(int i = 0; i < 4; i++) {
                    int mx = cur.x + dx[i];
                    int my = cur.y + dy[i];

                    if(mx < 0 || mx >= C || my <0 || my >= R || board[my][mx] == -1 )continue;
                    count++;
                    tempBoard[my][mx] += spread;

                }
                tempBoard[cur.y][cur.x] -= spread * count;
            }

            for(int i = 0 ; i < R; i++) {
                for(int j = 0 ; j < C;j++) {
                    board[i][j] += tempBoard[i][j];
                }
            }

            cleaningTopAir();
            cleaningBottomAir();

            for(int i = 0 ; i < R; i++) {
                for(int j = 0 ; j < C;j++) {
                    if(board[i][j] > 0) dirty.add(new Air(j,i,board[i][j]));
                }
            }
        }

        int answer = 2;

        for(int i = 0 ; i < R; i++) {
            for(int j = 0 ; j < C;j++) {
                answer += board[i][j];
            }
        }

        System.out.print(answer);

    }

    public static void cleaningTopAir() {
        for(int i = airU[0] - 1; i > 0; i--) {
            board[i][0] = board[i-1][0];
        }

        for(int i =0; i < C-1; i++) {
            board[0][i] = board[0][i+1];
        }

        for(int i = 0; i < airU[0] ; i++) {
            board[i][C-1] = board[i+1][C-1];
        }

        for(int i = C-1; i > 1; i--) {
            board[airU[0]][i] = board[airU[0]][i-1];
        }
        board[airU[0]][1] = 0;
    }
    public static void cleaningBottomAir() {
        for(int i = airD[0] + 1; i < R - 1; i++) {
            board[i][0] = board[i+1][0];
        }

        for(int i =0; i < C-1; i++) {
            board[R-1][i] = board[R-1][i+1];
        }

        for(int i = R-1; i > airD[0] ; i--) {
            board[i][C-1] = board[i-1][C-1];
        }

        for(int i = C-1; i > 1; i--) {
            board[airD[0]][i] = board[airD[0]][i-1];
        }
        board[airD[0]][1] = 0;
    }
}

SSAFY10-Class5-Algorithm / BOJ

[Java] 17144번 : 미세먼지 안녕! #33