[BOJ 17144] 미세먼지 안녕!

문제주소: 풀러가기

 

구사과씨의 방에 미세먼지가 가득하군요! 

공기청정기를 가동시키면 윗공기와 아랫공기가 순환을 하고 청정기로 들어간 공기는 깨끗한 공기로

바껴서 나오게 되네요~

 

풀고나니 이 문제의 핵심은 아래와 같이 두 가지 였던 것 같습니다.

1. 공기 확산을 하기 위해 BFS 를 활용할 줄 아는가?

2. 공기확산 후 대류를 시키기 위해 배열 인덱스를 잘 다룰 수 있는가?

2번은 아이디어에 의한 것이지만, 1번은 BFS에 적응되어 있지 않으면 힘들 수도 있겠네요!

2번을 해결하기 위해 달팽이수를 풀고나면 더 수월할 것 같습니다. 달팽이수 문제를 풀고난 뒤 이 문제를 풀게 되면, 배열 안의 요소를 회전시키는 게 익숙해질 거테니까요! 

각자 풀어보시고 참고를 위해 코드를 올립니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_연습_배열옮기기
{
    public static int                   R,C,T;
    public static int                   map[][];
    public static int                   tmap[][];

    public static BufferedReader        br;
    public static StringBuilder         sb;
    public static StringTokenizer       st;

    public static ArrayList    puri_pos;
    public static Queue<int[]>          q_dust;

    public static void init() throws Exception
    {
        br = new BufferedReader(new InputStreamReader(System.in));
        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];
        puri_pos = new ArrayList<>();
        q_dust   = new LinkedList<>();

        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(map[i][j] < 0) puri_pos.add(i);
                else if(map[i][j] > 0) q_dust.add(new int[]{i, j, map[i][j]});
            }
        }
    }

    public static boolean canSpread(int y, int x) { return (0 <= y && y < R) && (0 <= x && x < C) && (map[y][x] != -1);}
    public static int[][] spread_dir = { {-1, 0, 1, 0}, {0, 1, 0, -1} };
    public static void spread()
    {
        tmap = new int[R][C];           // 증감량을 저장해둬서 map[][] 에 더한다.
        while(!q_dust.isEmpty())
        {
            int[]               head    = q_dust.poll();
            int                 y       = head[0];
            int                 x       = head[1];
            int                 dust    = head[2];

            int                 spread_amount = dust / 5;

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

                if(canSpread(ny,nx))
                {
                    tmap[y][x]   -= spread_amount;
                    tmap[ny][nx] += spread_amount;
                }
            }
        }

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

    // 대류를 위해 이전 값을 모두 저장해둔다.
    public static int[][] cmap;
    public static void deepCopy()
    {
        cmap = new int[R][C];
        for (int i = 0; i < R; i++)
        {
            for (int j = 0; j < C; j++)
            {
                cmap[i][j] = map[i][j];
            }
        }
    }

    public static void purify_top()
    {
        int top_y = puri_pos.get(0);

        int i = top_y;
        int j = 1;

        map[i][j] = 0; // 공기청정기 바로 앞은 깨끗한 공기가 나온다!
        {
            for (int k = 0; k < C-2; k++)
            {
                j++;
                map[i][j] = cmap[i][j-1];
            }

            for (int k = 0; k < top_y; k++)
            {
                i--;
                map[i][j] = cmap[i+1][j];
            }

            for (int k = 0; k < C-1; k++)
            {
                j--;
                map[i][j] = cmap[i][j+1];
            }

            for (int k = 0; k < top_y-1; k++)
            {
                i++;
                map[i][j] = cmap[i-1][j];
            }
        }
    }

    public static void purify_bottom()
    {
        int btm_y = puri_pos.get(1);

        int i = btm_y;
        int j = 1;

        map[i][j] = 0; // 공기청정기 바로 앞은 깨끗한 공기가 나온다!
        {
            for (int k = 0; k < C-2; k++)
            {
                j++;
                map[i][j] = cmap[i][j-1];
            }

            for (int k = 0; k < R-btm_y-1; k++)
            {
                i++;
                map[i][j] = cmap[i-1][j];
            }

            for (int k = 0; k < C-1; k++)
            {
                j--;
                map[i][j] = cmap[i][j+1];
            }

            for (int k = 0; k < R-btm_y-2; k++)
            {
                i--;
                map[i][j] = cmap[i+1][j];
            }
        }
    }

    public static void findDust()
    {
        for (int i = 0; i < R; i++)
        {
            for (int j = 0; j < C; j++)
            {
                if(map[i][j] > 0)
                {
                    q_dust.add(new int[]{i, j, map[i][j]});
                }
            }
        }
    }

    public static int getRemainDust()
    {
        int remainDust = 0;
        for (int i = 0; i < R; i++)
        {
            for (int j = 0; j < C; j++)
            {
                if(map[i][j] > 0)
                {
                    remainDust += map[i][j];
                }
            }
        }

        return remainDust;
    }

    /*
        init(): 인풋을 받아옴과 동시에 공기청정기의 위치와 먼지의 위치를 알아냅니다.
        spread(): 먼지의 위치를 바탕으로 사방으로 먼지를 확산시킵니다.
        deepCopy(): 공기청정기를 가동시키면 미세먼지가 이동하기 때문에 기존의 미세먼지 정보를 저장
        purify_top() 과 bottom(): 윗공기와 아랫공기를 정화시킵니다.
        find_dust(): 초단위로 방에 존재하는 미세먼지의 위치를 업데이트합니다.
     */
    public static void main(String[] args) throws Exception
    {
        init();

        while(T-- > 0)
        {
            spread();

            deepCopy();
            purify_top();
            purify_bottom();

            findDust();
        }

        System.out.println(getRemainDust());    // 남은 미세먼지양을 계산합니다.
    }
}

시간은 1등과 약 2배 차이나네요...ㅎㅎ 방법은 비슷하던데.