백준 17144번 "미세먼지 안녕!"

백준 17144번 문제 "미세먼지 안녕!" 이다.

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

문제

---

예제 입출력

---

 

문제 접근

---

'미세먼지를 확산시키는 기능' 과 '공기청정기를 돌리는 기능' 2가지를 구현하기만 하면 된다.

 

 

1. 미세먼지를 확산시키는 기능

 

미세먼지의 확산은 모든 칸에서 동시에 일어나야 한다. 만약 원본 데이터가 있는 곳에서 먼지가 있는 칸마다 순차적으로 확산을 일으키면 이미 먼지가 있던 다른 칸에 먼지가 더해질 수도 있다. 이는 확산이 '동시에' 일어난다는 가정과 맞지 않는다.

 

5	0
9	0

예를 들어 위와 같이 먼지가 분포했다면, 동시에 확산이 일어난 다음에는

 

4	1
8	1

이 되어야 한다. 5에서 확산이 일어나 인접칸에 1씩 먼지가 더해지고, 9에서도 확산이 일어나 인접칸에 1씩 먼지가 더해지면서 5와 9가 서로 1씩 먼지를 주고받는 형태이다. 하지만 앞에서부터 순서대로 확산을 일으키면

 

5	1
6	2

5에서 먼저 확산이 일어나 9였던 칸이 10으로 변하고, 따라서 인접칸에 먼지를 2씩 확산시켜 원래와 다른 결과를 얻게 된다.

 

즉, 우리는 확산을 구현할 때 원본 데이터를 사용하는 것이 아니라 임시로 새 배열을 만들어 처리해야 한다는 것을 알 수 있다. 필자는 확산으로 인해 먼지가 줄어드는 양과 늘어나는 양을 새 배열에 저장한 다음, 확산이 끝나고 나면 저장해둔 변화량을 원본 배열에 반영하는 식으로 구현하였다.

 

 

2. 공기청정기를 돌리는 기능

 

공기청정기가 항상 가장 왼쪽 줄에 위치하며, 위아래 양 끝에는 위치하지 않으므로 구현하기 편리하다. 정말 문제 설명 그대로 먼지를 시계방향으로 한칸씩 이동시키고 공기청정기로 들어온 먼지는 없애주면 구현할 수 있다.

 

문제 풀이

---

아래는 풀이 코드이다.

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] space;
    static int R, C, T;
    static int circ_r;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    
    public static void main(String[] args) throws IOException {
        String[] first_input = br.readLine().split(" ");
        R = Integer.parseInt(first_input[0]);
        C = Integer.parseInt(first_input[1]);
        T = Integer.parseInt(first_input[2]);

        space = new int[R][C];
        for(int r = 0; r < R; r++) {
            String[] input = br.readLine().split(" ");
            for(int c = 0; c < C; c++) {
                int now = Integer.parseInt(input[c]);
                space[r][c] = now;
                if(now == -1) {circ_r = r;}
            }
        }

        for(int t = 0; t < T; t++) {
            diffuse();
            circulate();
        }

        System.out.print(sum_dust());     
    }

    static int sum_dust() {
        int ret = 0;
        for(int r = 0; r < R; r++) {
            for(int c = 0; c < C; c++) {
                if(space[r][c] == -1) {continue;}
                ret += space[r][c];
            }
        }
        return ret;
    }

    static void diffuse() {
        int[][] clone_arr = new int[R][C];
        for(int r = 0; r < R; r++) {
            for(int c = 0; c < C; c++) {
                int now_dust = space[r][c];
                if(now_dust == 0 || now_dust == -1) {continue;}
                int diffuse_dust = now_dust/5;
                
                for(int i = 0; i < 4; i++) {
                    int next_r = dr[i] + r;
                    int next_c = dc[i] + c;
                    if(0 > next_r || next_r >= R || 0 > next_c || next_c >= C) {continue;}
                    else if(space[next_r][next_c] == -1) {continue;}
                    else {
                        clone_arr[next_r][next_c] = diffuse_dust + clone_arr[next_r][next_c];
                        clone_arr[r][c] = clone_arr[r][c] - diffuse_dust;
                    }
                }
                
            }
        }

        for(int r = 0; r < R; r++) {
            for(int c = 0; c< C; c++) {
                if(space[r][c] == -1) {continue;}
                space[r][c] = space[r][c] + clone_arr[r][c];
            }
        }
    }

    static void circulate() {
        int[][] clone_arr = clone_space();
        
        for(int c = 1; c < C; c++) {
            clone_arr[circ_r-1][c] = c == 1 ? 0 : space[circ_r-1][c-1];
        }

        for(int r = circ_r-2; r >= 0; r--) {
            clone_arr[r][C-1] = space[r+1][C-1];
        }

        for(int c = C-2; c >= 0; c--) {
            clone_arr[0][c] = space[0][c+1];
        }

        for(int r = 1; r <= circ_r-1; r++) {
            clone_arr[r][0] = r == circ_r-1 ? -1 : space[r-1][0];
        }

        for(int c = 1; c < C; c++) {
            clone_arr[circ_r][c] = c == 1 ? 0 : space[circ_r][c-1];
        }

        for(int r = circ_r + 1; r < R; r++) {
            clone_arr[r][C-1] = space[r-1][C-1];
        }

        for(int c = C-2; c >= 0; c--) {
            clone_arr[R-1][c] = space[R-1][c+1];
        }

        for(int r = R-2; r >= circ_r; r--) {
            clone_arr[r][0] = r == circ_r ? -1 : space[r+1][0];
        }

        space = clone_arr;
    }

    static int[][] clone_space() {
        int[][] ret = new int[R][C];
        for(int r = 0; r < R; r++) {ret[r] = space[r].clone();}
        return ret;
    }
}

 

자세한 설명은 코드의 각 부분을 살펴보며 진행하도록 하자.

 

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] space;
    static int R, C, T;
    static int circ_r;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    
    public static void main(String[] args) throws IOException {
        String[] first_input = br.readLine().split(" ");
        R = Integer.parseInt(first_input[0]);
        C = Integer.parseInt(first_input[1]);
        T = Integer.parseInt(first_input[2]);

        space = new int[R][C];
        for(int r = 0; r < R; r++) {
            String[] input = br.readLine().split(" ");
            for(int c = 0; c < C; c++) {
                int now = Integer.parseInt(input[c]);
                space[r][c] = now;
                if(now == -1) {circ_r = r;}
            }
        }

 

문제를 푸는데 필요한 static 변수를 선언하고 입력값을 받는 과정이다. 여기서 circ_r 은 공기청정기가 위치한 행을 저장하는 용도로 사용되었다.

 

        for(int t = 0; t < T; t++) {
            diffuse();
            circulate();
        }

        System.out.print(sum_dust());

 

diffuse와 circulate, sum_dust 를 호출하여 문제 풀이를 끝냈다. 각 함수가 어떻게 구현되었는지 살펴보자.

 

1. diffuse

    static void diffuse() {
        int[][] clone_arr = new int[R][C];
        for(int r = 0; r < R; r++) {
            for(int c = 0; c < C; c++) {
                int now_dust = space[r][c];
                if(now_dust == 0 || now_dust == -1) {continue;}
                int diffuse_dust = now_dust/5;
                
                for(int i = 0; i < 4; i++) {
                    int next_r = dr[i] + r;
                    int next_c = dc[i] + c;
                    if(0 > next_r || next_r >= R || 0 > next_c || next_c >= C) {continue;}
                    else if(space[next_r][next_c] == -1) {continue;}
                    else {
                        clone_arr[next_r][next_c] = diffuse_dust + clone_arr[next_r][next_c];
                        clone_arr[r][c] = clone_arr[r][c] - diffuse_dust;
                    }
                }
                
            }
        }
        
        for(int r = 0; r < R; r++) {
            for(int c = 0; c< C; c++) {
                if(space[r][c] == -1) {continue;}
                space[r][c] = space[r][c] + clone_arr[r][c];
            }
        }
    }

 

원본 배열을 한칸씩 순회하다가 먼지가 있는 칸을 발견하면 clone_arr 에서 확산으로 인한 먼지의 변화량을 저장한다. i를 이용한 for 문에서 상하좌우 인접한 칸에 면지를 diffuse_dust 만큼 더하는 것을 확인할 수 있다. 그리고 확산을 일으킨 먼지는 확산시킨만큼 줄어든 변화량을 기록해주는 것도 확인하자.

 

앞선 2중 for문에서 clone_arr 에 먼지의 변화량을 모두 기록한 후에는 원본 배열 space에 먼지의 변화를 반영하고 함수가 끝난다.

 

 

2. circulate

    static void circulate() {
        int[][] clone_arr = clone_space();
        
        for(int c = 1; c < C; c++) {
            clone_arr[circ_r-1][c] = c == 1 ? 0 : space[circ_r-1][c-1];
        }

        for(int r = circ_r-2; r >= 0; r--) {
            clone_arr[r][C-1] = space[r+1][C-1];
        }

        for(int c = C-2; c >= 0; c--) {
            clone_arr[0][c] = space[0][c+1];
        }

        for(int r = 1; r <= circ_r-1; r++) {
            clone_arr[r][0] = r == circ_r-1 ? -1 : space[r-1][0];
        }

        for(int c = 1; c < C; c++) {
            clone_arr[circ_r][c] = c == 1 ? 0 : space[circ_r][c-1];
        }

        for(int r = circ_r + 1; r < R; r++) {
            clone_arr[r][C-1] = space[r-1][C-1];
        }

        for(int c = C-2; c >= 0; c--) {
            clone_arr[R-1][c] = space[R-1][c+1];
        }

        for(int r = R-2; r >= circ_r; r--) {
            clone_arr[r][0] = r == circ_r ? -1 : space[r+1][0];
        }

        space = clone_arr;
    }

circulate는 구현이 어려울게 없다. circ_r에 공기청정기의 아래부분 위치가 저장되어 있으므로 이 위치를 기준으로 하여 위쪽은 반시계, 아래쪽은 시계방향으로 칸을 이동시키면 된다.

 

    static int[][] clone_space() {
        int[][] ret = new int[R][C];
        for(int r = 0; r < R; r++) {ret[r] = space[r].clone();}
        return ret;
    }

 

 clone_space는 이름 그대로 space를 복사한 새 배열을 만드는 기능이다. (deep copy)

 

3. sum_dust

 

    static int sum_dust() {
        int ret = 0;
        for(int r = 0; r < R; r++) {
            for(int c = 0; c < C; c++) {
                if(space[r][c] == -1) {continue;}
                ret += space[r][c];
            }
        }
        return ret;
    }

공기청정기를 의미하는 -1 을 제외한 모든 먼지를 더하는 함수이다. 정답을 출력할 때 사용되었다.