[백준 17144] 미세먼지 안녕! - Java 문제풀이

오늘의 1일 1골드 문제는 다음 문제이다.

 

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

17144번: 미세먼지 안녕!

문제

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다. 즉, ⌊Ar,c/5⌋이다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - ⌊Ar,c/5⌋×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

왼쪽과 위쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

해설

문제에서 주어진 요구사항은 다음 3가지 이다.

1. 미세먼지가 확산되는 함수 생성

2. 공기청정기가 작동하는 함수 생성

3. 위 두 함수를 T번 반복

우선 나 같은 경우에는 에어컨의 윗부분의 행 번호를 나타내는 변수 airUp과, 아랫부분의 행 번호를 나타내는 변수 airDown을 이용해주었다.

1. 미세먼지가 확산되는 함수

미세먼지가 확산되는 함수는 간단하게 이중 for문을 돌며 확산을 시켜 주었다. 이 때, 해당 좌표에서 몇 개의 칸으로 번지는 지에 대한 정보를 저장해주어, 해당 좌표의 값을 저장해주었다.

static int[][] spreadDust(int[][] arr, int R, int C) {
    int[][] answer = new int[R][C];
    for(int i=0;i<R;i++) {
        for(int j=0;j<C;j++) {
            // 공기청정기이면 놉
            if (arr[i][j] == -1) {answer[i][j] = -1; continue;}
            int count = 0;
            int sp =  arr[i][j]/5;
            for(int k=0;k<4;k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (nx < 0 || nx >= R ||  ny < 0 || ny >= C || arr[nx][ny] == -1) continue;
                answer[nx][ny] += sp;
                count++;
            }
            answer[i][j] += arr[i][j] - sp * count;
        }
    }
    return answer;
}

 

2. 공기청정기가 작동하는 함수

공기청정기의 경우 위의 공기청정기는 반시계, 아래의 공기청정기는 시계방향으로 돈다. 예시로 위의 공기청정기만 있다고 가정해보겠다.

 

공기청정기가 반시계 방향으로 돈다는 것은, 다르게 말하면 데이터를 시계방향으로 돌면서 저장을 해주면 따로 다른 변수가 필요가 없다. 델타배열을 시계방향/혹은 반시계방향으로 설정해두어 k값을 1씩 증가시키거나 감소시키면서 방향을 바꿔주면 여러번의 if문이 필요가 없다.

또한, 반시계방향으로 돌다가 해당 에어컨이 있는 줄과 행이 같다면 방향을 바꾸는 작업도 필요하다.

 

마지막으로, 에어컨에서 나오는 곳은 0이고, 에어컨으로 들어가는 값은 정화되어 사라진다는 것을 염두에두면 된다 !

 

// 위 왼쪽 아래 오른쪽
static int[][] airConditionalOn(int[][] arr, int R, int C, int airUp, int airDown) {
    // 위쪽
    int i = airUp;
    int j = 0;
    int k = 0;
    boolean flag = true;
    do {
        int nx = i + dx[k];
        int ny = j + dy[k];
        if (nx <0 || nx >= R || ny < 0 || ny >= C || (k == 2 && i == airUp)) {
            k--;
            if (k<0) k=3;
        }
        else {
            arr[i][j]=arr[nx][ny];
            i = nx;
            j = ny;
        }
        if (i == airUp && j == 0 && k == 1) flag = false;
    } while(flag);

    // 아래쪽
    i = airDown;
    j = 0;
    k = 2;
    flag = true;
    do {
        int nx = i + dx[k];
        int ny = j + dy[k];
        if (nx <0 || nx >= R || ny < 0 || ny >= C|| (k == 0 && i == airDown)) {
            k++;
            if (k==4) k=0;
        }
        else {
            arr[i][j]=arr[nx][ny];
            i = nx;
            j = ny;
        }
        if (i == airDown && j == 0 && k == 1) flag = false;
    }while(flag);

    arr[airUp][0] = -1;
    arr[airUp][1] = 0;
    arr[airDown][0] = -1;
    arr[airDown][1] = 0;
    return arr;
}

 

3. 반복

위의 두 함수를 T번 반복하면 된다. 여기서 answer = 2로 한 이유는 에어컨의 경우 -1이기 때문에 이를 고려하여 먼저 2를 더한 후 시작해주었다.

다음은 코드의 전문이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_17144 {
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int R=Integer.parseInt(st.nextToken());
        int C=Integer.parseInt(st.nextToken());
        int T=Integer.parseInt(st.nextToken());
        int airUp = 0;
        int airDown = 0;
        int[][] arr = new int[R][C];
        for(int i=0;i<R;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<C;j++) arr[i][j] = Integer.parseInt(st.nextToken());
        }
        for(int i=0;i<R;i++) {
            if (arr[i][0] == -1) {
                airUp = i;
                airDown = i+1;
                break;
            }
        }
        for(int t=0;t<T;t++) {
            arr = spreadDust(arr, R, C);
            arr = airConditionalOn(arr, R, C, airUp, airDown);
        }
        int answer = 2;
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) answer+=arr[i][j];
        }
        System.out.println(answer);

    }
    static int[] dx = new int[]{-1, 0, 1, 0};
    static int[] dy = new int[]{0, -1, 0, 1};
    static int[][] spreadDust(int[][] arr, int R, int C) {
        int[][] answer = new int[R][C];
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                // 공기청정기이면 놉
                if (arr[i][j] == -1) {answer[i][j] = -1; continue;}
                int count = 0;
                int sp =  arr[i][j]/5;
                for(int k=0;k<4;k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx < 0 || nx >= R ||  ny < 0 || ny >= C || arr[nx][ny] == -1) continue;
                    answer[nx][ny] += sp;
                    count++;
                }
                answer[i][j] += arr[i][j] - sp * count;
            }
        }
        return answer;
    }

    // 위 왼쪽 아래 오른쪽
    static int[][] airConditionalOn(int[][] arr, int R, int C, int airUp, int airDown) {
        // 위쪽
        int i = airUp;
        int j = 0;
        int k = 0;
        boolean flag = true;
        do {
            int nx = i + dx[k];
            int ny = j + dy[k];
            if (nx <0 || nx >= R || ny < 0 || ny >= C || (k == 2 && i == airUp)) {
                k--;
                if (k<0) k=3;
            }
            else {
                arr[i][j]=arr[nx][ny];
                i = nx;
                j = ny;
            }
//            System.out.println("moveup"+i+" "+j+" "+k);
            if (i == airUp && j == 0 && k == 1) flag = false;
        } while(flag);

        // 아래쪽
        i = airDown;
        j = 0;
        k = 2;
        flag = true;
        do {
            int nx = i + dx[k];
            int ny = j + dy[k];
            if (nx <0 || nx >= R || ny < 0 || ny >= C|| (k == 0 && i == airDown)) {
                k++;
                if (k==4) k=0;
            }
            else {
                arr[i][j]=arr[nx][ny];
                i = nx;
                j = ny;
            }
//            System.out.println("movedown"+i+" "+j+" "+k);
            if (i == airDown && j == 0 && k == 1) flag = false;
        }while(flag);

        arr[airUp][0] = -1;
        arr[airUp][1] = 0;
        arr[airDown][0] = -1;
        arr[airDown][1] = 0;
        return arr;
    }
}

 

 

---

해당 문제를 푸는 데에는 총 1시간 18분(78분)이 소요되었다. 아무래도 구현문제를 오랜만에 풀어서 살짝 오래걸린 듯 하다.

또한 공기청정기가 도는 함수를 겹치는 부분을 수정할 수 있을 것 같긴 하여 추후 시간이 된다면 수정할 것이다.