[BOJ] 삼성 sw 역량 테스트 기출 :: 17144번 미세먼지 안녕! (java)

BOJ 17144 미세먼지 안녕! 자바(java) 풀이

• 랭크 : 골드5
• 백준 17144 미세먼지 안녕!
  
  
  

문제 정리

1. 집의 크기 RxC
2. 공기 청정기는 항상 1번 열에 설치, 두 행을 차지한다.
3. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있다.
4. 1초 동안 다음고 같은 일이 일어난다.
   ㄱ. 미세먼지 확산. 미세먼지가 있는 모든 칸에서 동시에 일어남
   • 네 방향으로 확산
   • 공기청정기가 있거나 칸이 없으면 확산 X
   • 확산 되는 양은 A(r,c) / 5 (소수점 버림)
   • (r,c)에 남은 미세먼지의 양은 A(r,c) - ( A(r,c)/5 )x 확산된 방향의 개수
     ㄴ. 공기 청정기 작동
   • 위쪽 공기 청정기의 바람은 반시계 방향 순환, 아래쪽 공기청정기의 바람은 시계방향 순환
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람. 공기청정기로 들어간 미세먼지는 모두 정화
     
     
     

문제 풀이

1. 처음에 값을 입력받으면서 미세먼지가 있는 곳을 모두 queue에 넣는다.
2. 같은 크기의 배열을 하나 더 만든다.
3. 큐에서 하나씩 빼면서 그 위치에 확산된 양을 빼고, 확산되는 양은 새로 만든 배열에 더한다.
4. 이렇게 반복한 다음 새로 만든 배열과 원래의 배열을 더한다.
5. 회전한다. 이때 공기청정기로 들어가는 미세먼지는 0으로 잘 처리한다.
6. 그리고 다시 미세먼지가 있는 곳을 모두 queue에 넣는다. 이를 반복한다.
   
   
   
7.  

백준 17144 미세먼지 안녕! 자바 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
class Pos{
    int x;
    int y;
    
    Pos(int x, int y){
        this.x = x;
        this.y = y;
    }
}
 
class Main {
 
    // 상, 하, 좌, 우
    static int[] xdir = {-1,1,0,0};
    static int[] ydir = {0,0,-1,1};
    static int R, C, T;
    static int[][] map, copy;
    static Queue<Pos> q;
    static Pos[] purifier;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        
        String[] temp = br.readLine().split(" ");
        R = Integer.parseInt(temp[0]);
        C = Integer.parseInt(temp[1]);
        T = Integer.parseInt(temp[2]);
        
        q = new LinkedList<>();
        map = new int[R][C];
        purifier = new Pos[2];
        int idx = 0;
        for(int i=0; i<R; i++) {
            temp = br.readLine().split(" ");
            for(int j=0; j<C; j++) {
                int num = Integer.parseInt(temp[j]);
                map[i][j] = num;
                
                // 미세먼지 이면
                if(map[i][j] > 0) {
                    q.offer(new Pos(i,j));
                }
                else if(map[i][j] == -1) {
                    purifier[idx++] = new Pos(i,j);
                }
            }
        }
        
        int time = 0;
        while(time < T) {
            copy = new int[R][C];
        
            // 확산
            diffusion();
            
            // 더하기
            for(int i=0; i<R; i++) {
                for(int j=0; j<C; j++) {
                    map[i][j] += copy[i][j];
                }
            }
            
            // 공기청정기 작동
            operation();
            
            // queue에 다시 넣기
            enqueue();
            time++;
        }
        
        System.out.println(getSum());
    }
    
    public static int getSum() {
        int sum = 0;
        
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(map[i][j] == -1) continue;
                sum += map[i][j];
            }
        }
        return sum;
    }
    public static void enqueue() {
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                // 미세먼지 이면
                if(map[i][j] > 0) {
                    q.offer(new Pos(i,j));
                }
            }
        }
    }
    
    public static void operation() {
        // 위쪽 회전
        int x = purifier[0].x;
        int y = purifier[1].y;
        
        Queue<Integer> q = new LinkedList<>();
        
        for(int i=1; y+i<C; i++) {
            q.offer(map[x][y+i]);
        }
        
        for(int i=x-1; i>=0; i--) {
            q.offer(map[i][C-1]);
        }
        
        for(int i=C-2; i>=0; i--) {
            q.offer(map[0][i]);
        }
        
        for(int i=1; i<x; i++) {
            q.offer(map[i][0]);
        }
        
        // 실제 회전
        map[x][y+1] = 0;    // 공기 청정기 바로 오른쪽은 미세먼지 0
        for(int i=2; y+i<C; i++) {
            map[x][y+i] = q.poll();
        }
        
        for(int i=x-1; i>=0; i--) {
            map[i][C-1] = q.poll();
        }
        
        for(int i=C-2; i>=0; i--) {
            map[0][i] = q.poll();
        }
        
        for(int i=1; i<x; i++) {
            map[i][0] = q.poll();
        }
        
        q.poll(); // 공기청정기로 사라짐
        
        // 아래쪽 회전
        x++;
        for(int i=1; y+i<C; i++) {
            q.offer(map[x][y+i]);
        }
        
        for(int i=x+1; i<R; i++) {
            q.offer(map[i][C-1]);
        }
        
        for(int i=C-2; i>=0; i--) {
            q.offer(map[R-1][i]);
        }
        
        for(int i=R-2; i>x; i--) {
            q.offer(map[i][0]);
        }
        
        
        // 실제 회전
        map[x][y+1] = 0;    // 공기 청정기 바로 오른쪽은 미세먼지 0
        for(int i=2; y+i<C; i++) {
            map[x][y+i] = q.poll();
        }
        
        for(int i=x+1; i<R; i++) {
            map[i][C-1] = q.poll();
        }
        
        for(int i=C-2; i>=0; i--) {
            map[R-1][i] = q.poll();
        }
        
        for(int i=R-2; i>x; i--) {
            map[i][0] = q.poll();
        }
        q.poll();
    }
    
    public static void diffusion() {
        while(!q.isEmpty()) {
            Pos p = q.poll();
            int x = p.x;
            int y = p.y;
            int amount = map[x][y] / 5;
            
            for(int i=0; i<4; i++) {
                int dx = x + xdir[i];
                int dy = y + ydir[i];
                
                // 벗어나지 않는지? 공기청정기 위치는 아닌지 check
                if(isValidPosition(dx, dy)) {
                    copy[dx][dy] += amount;
                    map[x][y] -= amount;
                }
            }
        }
    }
    
    public static boolean isValidPosition(int x, int y){
        if(x < 0 || x >= R || y < 0 || y >= C) return false;
        if((x == purifier[0].x && y == purifier[0].y) || (x == purifier[1].x && y == purifier[1].y)) return false;
        return true;
    }
}