[백준/JAVA] 17144번: 미세먼지 안녕!

📖 문제

17144번: 미세먼지 안녕!

 

 

💡  풀이 방식

• 시뮬레이션

1. 집 정보를 입력받으면서, 공기청정기 위치 cleaner도 함께 입력받는다.

2. T초 동안 아래 과정을 반복한다.

  → 1) 미세먼지 위치와 미세먼지 양을 확인해 큐에 저장한다. (❌ 미세먼지 위치만 저장❌ 나중에 격자에서 해당 칸 값 map[i][j] 받아와서 기존 배열을 바로 수정하게 되면 틀린다.)

  → 2) 모든 미세먼지가 있는 칸을 돌며 먼지를 확산시킨다. 이 때, 확산될 먼지가 없다면 = 해당 칸의 값이 5보다 작다면 패스한다.

  → 3) 공기 청정기를 작동시킨다.

       ┕ 위쪽 공기 청정는 반시계 방향 순환시키고, 공기 청정기에서 부는 바람은 미세먼지가 사라진 처리 (map[cleaner][1] = 0) 한다.

       ┕ 위쪽 공기 청정는 시계 방향 순환시키고, 공기 청정기에서 부는 바람은 미세먼지가 사라진 처리 (map[cleaner + 1][1] = 0) 한다.

 

 

💥 유의사항

- 먼지의 위치는 매번 1초마다 한 번씩 확인해줘야 한다.

- 미세먼지 확산 시 기존 배열을 바로 수정하지 않는 것 ! 큐에 (행, 열) 값만 저장하고, 확산시킬 때 map[행][열] 이렇게 기존 배열의 값을 가져와서 바로 수정하면 틀린다... (이것 땜에 2시간 날림) (참고)

- 테두리 회전 = 격자 밀 때 "당기기"의 개념으로 생각하는 것이 좋다.

- 공기청정기에서 부는 바람은 미세먼지가 없음(0) 처리를 해줘야 한다!

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {1, 0, -1, 0};
    
    static int R, C, T;
    static int[][] map;
    static int cleaner = -1;   // 공기 청정기 위치
    
    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];
        
        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;
            }
        }
        
        while(T --> 0) {
            diffuse();
            work();
        }
        
        calculate();
    }
    
    // 1. 미세먼지 4방향 확산시키기
    private static void diffuse() {
        // 1) 미세먼지 위치 저장하기
        Queue<int[]> dusts = new ArrayDeque<>();
        
        for(int i = 0 ; i < R ; i++) {
            for(int j = 0 ; j < C ; j++) {
                if(map[i][j] == 0 || map[i][j] == -1)   continue;
                dusts.add(new int[]{i, j, map[i][j]});  // 🔔 (i,j) 만 넣고 나중에 map[i][j] 쓰려면 틀린다!!!!!!!!
            }
        }
        
        // 2) 미세먼지 확산하기
        while(!dusts.isEmpty()) {
            int[] now = dusts.poll();
            
            if(now[2] < 5) continue;   // 🔔 확산될 먼지 없으면 패스
            
            int cnt = 0;   // 확산되는 방향 수
            int dust = now[2] / 5;   // 확산되는 양
            
            for(int dir = 0 ; dir < 4 ; dir++) {
                int nr = now[0] + dx[dir];
                int nc = now[1] + dy[dir];
                
                // 인접 위치에 공기청정기 있거나, 칸이 없으면 X
                if(nr < 0 || nr >= R || nc < 0 || nc >= C)  continue;
                if(map[nr][nc] == -1) continue;
                
                map[nr][nc] += dust;
                ++cnt;
            }
            
            map[now[0]][now[1]] -= dust * cnt;
        }
    }
 
    // 2. 공기 청정기 작동 (= 테두리 회전)
    private static void work() {
        // [1] 위쪽 공청 = 반시계 방향 순환
        int top = cleaner;
        
        // 1) 아래로 당기기
        for(int i = top - 1 ; i > 0 ; i--)    map[i][0] = map[i-1][0];
        
        // 2) 왼쪽으로 당기기
        for(int i = 0 ; i < C - 1 ; i++)    map[0][i] = map[0][i+1];
        
        // 3) 위로 당기기
        for(int i = 0 ; i < top ; i++)    map[i][C-1] = map[i+1][C-1];
        
        // 4) 오른쪽으로 당기기
        for(int i = C - 1 ; i > 1 ; i--)    map[top][i] = map[top][i-1];
            
        map[top][1] = 0;    // ⭐ 공기청정기에서 부는 바람은 미세먼지 X
                
                
        // [2] 아래쪽 공청 = 시계 방향 순환
        int down = cleaner + 1;
        
        // 1) 위로 당기기
        for(int i = down + 1 ; i < R - 1 ; i++)    map[i][0] = map[i+1][0];
        
        // 2) 왼쪽으로 당기기
        for(int i = 0 ; i < C - 1 ; i++)    map[R-1][i] = map[R-1][i+1];
            
        // 3) 아래로 당기기
        for(int i = R - 1 ; i > down ; i--)    map[i][C-1] = map[i-1][C-1];
        
        // 4) 오른쪽으로 당기기
        for(int i = C - 1 ; i > 1 ; i--)    map[down][i] = map[down][i-1];
            
        map[down][1] = 0;   // ⭐ 공기청정기에서 부는 바람은 미세먼지 X
    }
    
    private static void calculate() {
        int total = 0;
        
        for(int[] i : map) {
            for(int j : i) {
                if(j == -1) continue;
                total += j;
            }
        }
        
        System.out.println(total);
    }
}
 

 

 

➕ 다른 풀이 방식

- 임시 배열에 값 만들어서 활용하셨고, while문으로 회전시키셨다. (추구미..)

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

 

---

💦 어려웠던 점

- 배열 한 칸씩 회전시킬 때 당기는 개념은 인지하고 있었는데 while문 활용해서 방향 설정을 어떻게 해야할지 고민을 오래 했다. 배열 미는 문제를 다시 더 풀어봐겠다,,

- 매번 미세먼지의 위치와 값을 확인해서 리스트에 저장하고 활용할 생각을 하지 못 했다.

 

 

 

🧐 새로 알게 된 내용

- "동시에 확산"시킬 때는 임시 배열 만들어 활용하거나, 큐에 좌표값이랑 value까지 함께 저장해서 배열의 값을 바로 수정하지 않도록 해야겠다,,,ㅎㅎ

또 보기,,

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[BOJ] 17144.미세먼지 안녕!(시뮬레이션).java