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

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

17144번: 미세먼지 안녕!

 

알고리즘 분류

• 구현
• 시뮬레이션

내가 정리한 문제의 요점은 다음과 같다.

 

1. 확산 단계 (Spread 메서드)

 - 미세먼지가 있는 상, 하, 좌, 우로 확산이 되며 확산되는 양은 map[r][c] /5 만큼이고 확산된 방향만큼 map[r][c]의 양이 줄어든다 (map[r][c]/5) * 확산된 방향의 수 // 다른 곳에서도 같은 칸에 확산되는 경우 누적 계산

 (단, 공기청정기가 있는 곳이거나 범위에서 벗어난 곳은 확산 X, 빈칸일 경우만 확산)

2. 공기 청정 단계 (Cleaner 메서드)

 2-1 공기청정기의 상단 좌표부터 반시계 방향으로 미세먼지를 한 칸씩 밀어낸다.

 2-2 공기청정기의 하단 좌표부터 시계 방향으로 미세먼지를 한칸씩 밀어낸다.

 

3. 확산-공기 청정 단계를 마친 후 미세먼지를 다시 파악한다. (DustBatch 메서드)

 

4. 반복 횟수만큼 실행 후 남아 있는 미세 먼지를 계산 (ArraySum 메서드)

 

import java.util.*;

public class Main {

    static int R,C,T,tx,ty,bx,by;
    static int[][] map;
    static int[] dr = {-1,0,1,0};
    static int[] dc = {0,-1,0,1};
    static Queue<Point> dust;
    static ArrayList<Point> filter;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);       
        
        R = sc.nextInt();
        C = sc.nextInt();
        T = sc.nextInt();
        
        map = new int[R][C];
        dust = new LinkedList<Point>();
        filter = new ArrayList<Point>();
        
        for(int r = 0; r<R; r++)
        {
            for(int c = 0; c<C; c++)
            {
                map[r][c] = sc.nextInt();
                if(map[r][c]==-1) {
                    filter.add(new Point(r,c));
                }
            }
        }
        
        Collections.sort(filter,new Comparator<Point>() {
            public int compare(Point p1, Point p2) {
                return p1.x-p2.x;
            }
        });
                
        tx = filter.get(0).x;
        ty = filter.get(0).y;
        bx = filter.get(1).x;
        by = filter.get(1).y;
        
        int[] tp = {3,0,1,2};
        int[] bp = {3,2,1,0};
        
        while(T-->0) {
            dustBatch();
            Spread();
            //PrintArray(map);
            Cleaner(tx,ty,tp);
            //PrintArray(map);
            Cleaner(bx,by,bp);
            //PrintArray(map);            
        }
        
        System.out.println(ArraySum());
        
        sc.close();

    }

    //미세 먼지 위치 다시 배치
    private static void dustBatch()
    {
        dust.clear();
        for(int r = 0; r<R; r++)
        {
            for(int c = 0; c<C; c++)
            {
                if(map[r][c] > 0) {
                    dust.add(new Point(r,c));
                }
            }
        }
    }

    //1. 확산
    private static void Spread()
    {
        int[][] temp = new int[R][C];
        
        temp[tx][ty] = -1;
        temp[bx][by] = -1;
        
        int size = dust.size();
        
        for(int sz =0; sz<size;sz++)
        {
            Point p = dust.poll();
            
            int r = p.x;
            int c = p.y;
            
            int cnt =0;
            for(int cycle = 0; cycle<4;cycle++)
            {
                int cr = r+dr[cycle];
                int cc = c+dc[cycle];                
                
                if(cr>=0 && cr<R && cc>=0 && cc < C && map[cr][cc]!=-1) {
                    cnt++;
                    temp[cr][cc]+= map[r][c]/5;
                    dust.offer(new Point(cr,cc));
                }
            }

            if(cnt!=0) {
             temp[r][c]+= map[r][c] - ((map[r][c]/5)*cnt);   
            }
        }
        map = ArrayCopy(temp);
    }
    
    //2. 공기 청정 작업
    private static void Cleaner(int x, int y, int[] dir)
    {
        int[][] temp = ArrayCopy(map);
                
        int CleanerX = x;
        int CleanerY = y+1;
        
        map[CleanerX][CleanerY] = 0;                
        
        for(int cycle =0; cycle<4;cycle++)
        {
            
            while(true)
            {
                int cx = CleanerX + dr[dir[cycle]];
                int cy = CleanerY + dc[dir[cycle]];
                
                if( cx <0 || cx>=R || cy <0 || cy>=C ) {
                    break;
                }
                
                if(cx == x && cy == y) {
                    break;
                }
                
                map[cx][cy] = temp[CleanerX][CleanerY];
                CleanerX = cx;
                CleanerY = cy;
            }
        }
    }
    
    private static void PrintArray(int[][] temp) {
        System.out.println("");
        
        for(int r =0; r<R;r++)
        {
            for(int c =0; c<C;c++) {
                System.out.printf("%3d ", temp[r][c]); 
            }
            System.out.println("");
        }
        System.out.println("");
    }
    private static int[][] ArrayCopy(int[][] origin)
    {
        int[][] temp = new int[R][C];
        
        for(int r =0; r<R;r++)
        {
            for(int c =0; c<C;c++) {
                temp[r][c] = origin[r][c];
            }
        }
        return temp;
    }
    
    private static int ArraySum()
    {
        int answer = 0;
        for(int r =0; r<R;r++)
        {
            for(int c =0; c<C;c++) {
                if(map[r][c]>0)
                {
                    answer+= map[r][c];
                }
            }
        }
        return answer;
    }
}
class Point{
    int x;
    int y;
    
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

 

시뮬레이션은 디버그를 해가면서 정확히 코드가 의도한 대로 동작하는지 확인하는 과정이 너무 힘든 것 같다..

Scanner를 사용하지 않고 다른 클래스를 사용하면 시간 단축 여지는 더 있는 듯하다