[백준] 17144번 : 미세먼지 안녕! - 자바[Java]

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

17144번: 미세먼지 안녕!

풀이

문제에서 주어진 대로 구현하면 된다.

 

주의해야 할 점

먼지를 확산시킬 때 순서 없이 모든 먼지 확산이 동시에 일어나 최종적인 결과를 map에 저장해야 했다. 따라서 먼지가 확산된 결과를 저장하는 2차원 배열 int[][] map을 생성하고, 확산하기 전 먼지의 위치와 양을 저장하는 자료구조 ArrayDeque<Data> dust를 따로 생성하였다.

따라서 먼지 확산 전 map은 모두 0으로 초기화되어야하며, 먼지 확산과 공기청정기를 작동시킨 후에는 새로운 먼지의 위치와 양을 dust에 추가해야 한다.

 

1. initMap(): map을 0으로 초기화

2. spread(): 먼지 확산 - dust로 map을 업데이트하고, 확산이 완료되면 dust는 빈 상태가 된다. 

3. clean(): 공기청정기 - map을 업데이트한다.

4. makeDust(): map으로 dust에 데이터 추가

5. sum(): map을 사용하여 남은 먼지 양을 구한다.

 

코드

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

public class Main {

    static class Data {
        int r, c, num;

        public Data(int r, int c, int num) {
            this.r = r;
            this.c = c;
            this.num = num;
        }
    }

    static int r, c;
    static int[][] map; // 먼지가 있는 맵
    static ArrayDeque<Data> dust = new ArrayDeque<>(); // 먼지 위치와 양
    static int[] cleaner = new int[2]; // 공기 청정기 위치

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

        map = new int[r][c];

        int idx = 0;
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                int num = Integer.parseInt(st.nextToken());
                if (num == -1) {
                    cleaner[idx++] = i;
                }
                else if (num > 0) {
                    dust.add(new Data(i, j, num));
                }
            }
        }

        while (t-- > 0) {
            initMap(); // map을 0으로 초기화
            spread(); // 먼지확산 - dust로 map 업데이트, 이 때 dust를 비운다
            clean(); // 공기청정기 - map 업데이트
            makeDust(); // map으로 dust 채우기
        }

        bw.write(sum()+ ""); // map으로 남아있는 먼지의 양을 구한다
        bw.flush();

        br.close();
        bw.close();
    }

    static void print() { // 출력용 메서드
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    static void initMap() {
        for (int i = 0; i < r; i++) {
            Arrays.fill(map[i], 0);
        }
    }

    static void spread() {
        while (!dust.isEmpty()) {
            Data data = dust.poll();
            int x = data.r;
            int y = data.c;
            int num = data.num;

            int sum = 0;

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 범위 체크, 공기청정기 체크 후 map에 확산된 먼지의 양을 더한다
                if (!checkIndex(nx, ny)) continue;
                if (ny == 0 && (nx == cleaner[0] || nx == cleaner[1])) continue;

                map[nx][ny] += num / 5;
                sum += num / 5;
            }

            map[x][y] += num - sum; // 현재 먼지의 양을 더한다
        }
    }

    static boolean checkIndex(int x, int y) {
        return x >= 0 && x < r && y >= 0 && y < c;
    }

    static void clean() {
        // 위쪽 순환
        int curR = cleaner[0] - 2;
        int curC = 0;

        while (curR >= 0) {
            map[curR+1][curC] = map[curR][curC];
            curR--;
        }
        curR++;
        curC++;
        while (curC < c) {
            map[curR][curC-1] = map[curR][curC];
            curC++;
        }
        curC--;
        curR++;
        while (curR < cleaner[1]) {
            map[curR-1][curC] = map[curR][curC];
            curR++;
        }
        curR--;
        curC--;
        while (curC >= 1) {
            map[curR][curC+1] = map[curR][curC];
            curC--;
        }
        map[cleaner[0]][1] = 0; // 바람이 나오는 위치

        // 아래쪽 순환
        curR = cleaner[1] + 2;
        curC = 0;

        while (curR < r) {
            map[curR-1][curC] = map[curR][curC];
            curR++;
        }
        curR--;
        curC++;
        while (curC < c) {
            map[curR][curC-1] = map[curR][curC];
            curC++;
        }
        curC--;
        curR--;
        while (curR > cleaner[0]) {
            map[curR+1][curC] = map[curR][curC];
            curR--;
        }
        curR++;
        curC--;
        while (curC >= 1) {
            map[curR][curC+1] = map[curR][curC];
            curC--;
        }
        map[cleaner[1]][1] = 0; // 바람이 나오는 위치
    }

    static void makeDust() {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] > 0) {
                    dust.add(new Data(i, j, map[i][j]));
                }
            }
        }
    }

    static int sum() {
        int sum = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] > 0) sum += map[i][j];
            }
        }

        return sum;
    }
}

 

다른 풀이

https://www.acmicpc.net/source/65134905

https://data-make.tistory.com/524

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ17144 {
 
    static int R, C, T, map[][];
    static int cleaner = -1;
    static Queue<Dust> dusts;
    static int[] dx = {0, -1, 0, 1}, dy = {1, 0, -1, 0};
    static class Dust {
        int x, y, w;
 
        public Dust(int x, int y, int w) {
            super();
            this.x = x;
            this.y = y;
            this.w = w;
        }
        
    }
    
    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()); // 행
        C = Integer.parseInt(st.nextToken()); // 열
        T = Integer.parseInt(st.nextToken()); // 초
        map = new int[R][C];
        
        // map 정보 저장
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                
                // 공기청정기 위치 저장    
                if(cleaner == -1 && map[i][j] == -1) {
                    cleaner = i;
                }
            }
        }
        
        for (int time = 0; time < T; time++) {
            
            // 미세먼지가 있는 공간 확인
            checkDust();
            
            // 미세먼지 확산
            spread();
            
            // 공기청정기 작동
            operate();
 
        }
        
        int res = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j] == -1) continue;
                res += map[i][j];
            }
        }
        
        System.out.println(res);
    }
 
    private static void checkDust() {
        
        dusts = new LinkedList<>();
        
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j] == -1 || map[i][j] == 0) continue;
                // 미세먼지가 있는 공간과 미세먼지 양
                dusts.add(new Dust(i, j, map[i][j]));
            }
        }
        
    }
 
    private static void spread() {
        
        while(!dusts.isEmpty()) {
            
            Dust now = dusts.poll();
            // 확산될 먼지가 없으면
            if(now.w < 5) continue;
            // 확산되는 양은 Ar,c/5
            int amountOfSpread = now.w / 5;
            int cnt = 0;
            // 인접한 방향으로 확산
            for (int d = 0; d < 4; d++) {
                int xx = now.x + dx[d];
                int yy = now.y + dy[d];
                // 범위를 벗어나면
                if(xx < 0 || xx >= R || yy < 0 || yy >= C) continue;
                // 공기청정기가 있으면
                if(map[xx][yy] == -1) continue;
                
                map[xx][yy] += amountOfSpread;
                ++cnt;
            }
            
            // 남은 미세먼지 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수)
            map[now.x][now.y] -= amountOfSpread * cnt;
        }
        
    }
 
    // 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동
    private static void operate() {
        
        int top = cleaner;
        int down = cleaner + 1;
        
        // 위쪽 공기청정기의 바람은 반시계방향 순환,
        // 아래로 당기기
        for (int i = top - 1; i > 0; i--) 
            map[i][0] = map[i-1][0];
        // 왼쪽으로 당기기
        for (int i = 0; i < C - 1; i++) 
            map[0][i] = map[0][i+1];
        // 위로 당기기
        for (int i = 0; i < top; i++) 
            map[i][C - 1] = map[i + 1][C - 1];
        // 오른쪽으로 당기기
        for (int i = C - 1; i > 1; i--) 
            map[top][i] = map[top][i-1];
        // 공기청정기에서 부는 바람은 미세먼지가 없는 바람
        map[top][1] = 0;
        
        // 아래쪽 공기청정기의 바람은 시계방향으로 순환
        // 위로 당기기
        for (int i = down + 1; i < R - 1; i++) 
            map[i][0] = map[i + 1][0];
        // 왼쪽으로 당기기
        for (int i = 0; i < C - 1; i++) 
            map[R - 1][i] = map[R - 1][i + 1]; 
        // 아래로 당기기
        for (int i = R - 1; i > down; i--) 
            map[i][C - 1] = map[i - 1][C - 1];
        // 오른쪽으로 당기기
        for (int i = C - 1; i > 1; i--) 
            map[down][i] = map[down][i - 1];
        // 공기청정기에서 부는 바람은 미세먼지가 없는 바람
        map[down][1] = 0;
    }
    
}