[BOJ 17144] 미세먼지 안녕!

문제출처

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

17144번: 미세먼지 안녕!

 

문제풀이

그냥 진짜 구현하는 문제다. 빡구현까지는 아니고 배열 조정을 하느라 약간 머리가 아픈 문제

문제에 나온대로 확산과 공기청정기 순환 2가지로 나눠서 구현하면 된다.

 

spreadDust() 메서드

확산은 tempMap배열을 이용해 구현했다. 확산은 queue를 이용해도 될것같다.

확산과 같은 경우 인접한 공간에 숫자가 있는경우 어떻게 처리하는지가 중요하다. 한 공간(y, x)를 기준으로 인접한 공간에 값이 없다면 그냥 4방향으로 확산시켜주면 되지만, 한 방향이라도 있는 경우 다음 탐색을 할때 영향을 주기 때문이다. 즉, 우리는 순차적으로 한 공간(y, x)에 대해 확산시키는 소스를 구현하지만 문제는 한순간에 확산하기 때문에 영향을 받기전의 값으로 확산을 시켜야 한다.

 

1. map을 tempMap에 복사하여 원래의 미세먼지 값들을 저장.

2. 확산될 먼지의 양은 원본map을 통해 계산

3. tempMap에서 먼지를 확산시킴

4. tempMap에서 확산시킨 것들 다시 map으로 옮김.

 

activateAirCleaner() 메서드

이 부분은 공기청정기를 작동시키는 메서드이다. 기존 입력을 받을때 따로 list에 저장해둔 공기청정기의 y좌표를 이용해 map배열의 값을 옮겨주면 된다. 공기청정기에 들어가는 먼지는 없어진다는 조건을 활용해서 없어지는 좌측부터 하나씩 값을 옮겨주었다. 여기서 주의할 점은 공기청정기가 위치한 y좌표의 x축을 이동시킬때 모두 이동시키고 공기청정기 다음x좌표를 0으로 다시 갱신해줘야 한다는 것이다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_17144/boj17144.java

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

public class Main {
    private static int r, c, t;
    private static int dy[] = {0, -1, 0, 1};
    private static int dx[] = {1, 0, -1, 0};
    private static int map[][];
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;
    private static ArrayList<Integer> cleaner;

    public static void main(String[] args) throws Exception {
        init();
        while (true) {
            t--;
            spreadDust();
            activateAirCleaner();

            if (t == 0) {
                System.out.println(countDustVolumn());
                break;
            }
        }
    }

    private static int countDustVolumn() {
        int ret = 0;
        for (int y=0; y<r; y++) {
            for (int x=0; x<c; x++) {
                if (map[y][x] != 0 && map[y][x] != -1) ret += map[y][x];
            }
        }
        return ret;
    }

    private static void copyMap(int src[][], int dest[][]) {
        for (int y=0; y<r; y++) {
            for (int x=0; x<c; x++) {
                dest[y][x] = src[y][x];
            }
        }
    }

    private static void activateAirCleaner() {
        int upY = cleaner.get(0);
        int downY = cleaner.get(1);

        // 위쪽
        for (int y=upY-1; y>0; y--) {
            map[y][0] = map[y-1][0];
        }
        for (int x=0; x<c-1; x++) {
            map[0][x] = map[0][x+1];
        }
        for (int y=0; y<upY; y++) {
            map[y][c-1] = map[y+1][c-1];
        }
        for (int x=c-1; x>0; x--) {
            map[upY][x] = map[upY][x-1];
        }
        map[upY][1] = 0;

        // 아래쪽
        for (int y=downY+1; y<r-1; y++) {
            map[y][0] = map[y+1][0];
        }
        for (int x=0; x<c-1; x++) {
            map[r-1][x] = map[r-1][x+1];
        }
        for (int y=r-1; y>=downY; y--) {
            map[y][c-1] = map[y-1][c-1];
        }
        for (int x=c-1; x>1; x--) {
            map[downY][x] = map[downY][x-1];
        }
        map[downY][1] = 0;
    }

    private static void spreadDust() {
        int tempMap[][] = new int[r][c];
        copyMap(map, tempMap);

        for (int y=0; y<r; y++) {
            for (int x=0; x<c; x++) {
                if (map[y][x] != 0 && map[y][x] != -1) {
                    int count = 0;
                    int dust = map[y][x] / 5;
                    for (int i=0; i<4; i++) {
                        int ny = y+dy[i];
                        int nx = x+dx[i];

                        if (ny<0 || nx<0 || ny>=r || nx>=c || map[ny][nx] == -1) continue;
                        tempMap[ny][nx] += dust;
                        count++;
                    }
                    tempMap[y][x] -= (count * dust);
                }
            }
        }
        copyMap(tempMap, map);
    }

    private static void init() throws Exception {
        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];
        cleaner = new ArrayList<>();

        for (int y=0; y<r; y++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int x=0; x<c; x++) {
                map[y][x] = Integer.parseInt(st.nextToken());
                if (map[y][x] == -1) cleaner.add(y);
            }
        }
    }
}