[백준] 17144 미세먼지 안녕! (JAVA)

문제 링크:

17144번: 미세먼지 안녕!

 

 

난이도: 골드4

 

 

문제:

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 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번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

 

 

출력:

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

 

 

문제 이해:

작성자는 문제 이해만 오랜 시간이 걸렸다.

이해를 더 쉽게 하기 위해 예제입력 1로 예를 들어보자

7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

우선 1초에 한번씩 확산이 일어난다. 확산이 일어나면 문제에 적혀져있는 확산 방식으로 인해 다음과 같이 변한다.

확산이 일어난 이후 공기청정기가 작동한다 여기가 핵심이다.

즉 다음과 같이 두 방향으로 한칸씩 미세먼지가 이동한다.

한칸씩 밀리며 다음과 같이 변화된다.

이를 입력한 T초까지 반복하여 남아있는 미세먼지 양을 출력하는 것이 문제이다.

 

 

 

구현 방향:

이 문제는 특정 알고리즘이 없이 직접 구현하는 방식이기에 작성자는 다음과 같이 구현하였다.

 

큰 틀은 이렇다.

1. 초기값 세팅

2. 확산

3. 공기청정기 실행

4. 미세먼지 양 측정

 

여기서 주의할 점은 확산은 동시에 일어나기 때문에 확산된 값을 갱신하면서 반복하는 것이 아닌,

누적 값만 다른 배열에 저장하고 모두 반복한 후에 덮어쓰는 방식으로 진행해야한다.

 

이를 코드로 구현하면 다음과 같다.

 

 

정답 코드:

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

public class Main {
    static int R,C,T;
    static int[][] matrix;
    static int[][] temp;
    static int []wind1={-1,-1};
    static int []wind2={-1,-1};
    static int []dx={-1,1,0,0};
    static int []dy={0,0,-1,1};
    static int result;

    public static void solve(){
        //T 초까지 진행
        for(int i=0; i<T; i++){
            //확산
            spread();
            //확산 결과(temp)를 matrix에 반영
            for (int j = 0; j < R; j++) {
                System.arraycopy(temp[j], 0, matrix[j], 0, C);
            }
            //확산 후 바람 전파
            wind();

        }
        //결과 수치량 출력
        sumResult();
    }

    //1초 확산하는 메서드
    public static void spread(){
        temp = new int[R][C];

        for (int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                if (matrix[i][j] == -1) { // 청정기 위치 유지
                    temp[i][j] = -1;
                    continue;
                }
                int count=0; //전파 할 수 있는 개수
                //상 하 좌 우 탐색
                for(int d=0; d<4; d++){
                    int nx= i+dx[d];
                    int ny= j+dy[d];

                    //벽이나 공기청정기인 경우
                    if(nx<0 || ny<0 || nx>=R || ny>=C || matrix[nx][ny]==-1) continue;

                    //아닌경우 확산 값 더하기
                    count++;
                    // ⌊Ar,c/5⌋
                    temp[nx][ny]+=matrix[i][j]/5;
                }

                //(r, c)에 남은 미세먼지의 양은 Ar,c - ⌊Ar,c/5⌋×(확산된 방향의 개수) 이다
                temp[i][j]+= matrix[i][j]-(matrix[i][j]/5) * count;
            }

        }

    }
    
    //바람 전파
    public static void wind() {
        int[][] temp1 = new int[R][C];
        for (int i = 0; i < R; i++) {
            System.arraycopy(matrix[i], 0, temp1[i], 0, C);
        }

        int up = wind1[0];
        int down = wind2[0];

        // 위쪽(반시계)
        for (int i = C - 1; i > 1; i--) matrix[up][i] = temp1[up][i - 1]; // 오른쪽
        for (int i = 0; i < up; i++) matrix[i][C - 1] = temp1[i + 1][C - 1]; // 위로
        for (int i = 0; i < C - 1; i++) matrix[0][i] = temp1[0][i + 1]; // 왼쪽
        for (int i = up - 1; i > 0; i--) matrix[i][0] = temp1[i - 1][0]; // 아래로
        matrix[up][1] = 0; matrix[up][0] = -1;

        // 아래쪽(시계)
        for (int i = C - 1; i > 1; i--) matrix[down][i] = temp1[down][i - 1]; // 오른쪽
        for (int i = R - 1; i > down; i--) matrix[i][C - 1] = temp1[i - 1][C - 1]; // 아래로
        for (int i = 0; i < C - 1; i++) matrix[R - 1][i] = temp1[R - 1][i + 1]; // 왼쪽
        for (int i = down + 1; i < R - 1; i++) matrix[i][0] = temp1[i + 1][0]; // 위로
        matrix[down][1] = 0; matrix[down][0] = -1;
    }
    

    public static void sumResult(){
        int sum=0;
        for (int i=0; i<R; i++){
            for(int j=0; j<C; j++) {
                if(matrix[i][j]==0 || matrix[i][j]==-1) continue;
                sum+=matrix[i][j];
            }
        }
        result=sum;
    }

    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());

        R=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        T=Integer.parseInt(st.nextToken());

        matrix=new int[R][C];
        temp=new int[R][C];

        for (int i=0; i<R; i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0; j<C; j++){
                matrix[i][j]=Integer.parseInt(st.nextToken());
                if (matrix[i][j] == -1) {
                    if (wind1[0] == -1) {
                        wind1[0] = i; wind1[1] = j;
                    } else {
                        wind2[0] = i; wind2[1] = j;
                    }
                }
            }

        }

        //초기 세팅 끝


        //탐색 시작
        solve();

        //결과 출력
        System.out.println(result);
    }
}

 

 

마무리하먀:

골드 4단계 문제라 정답률이 높아 쉽게 풀 수 있을 거라 생각했지만, 예상과 달리 가장 오랜 시간이 걸린 문제였다.
문제가 길거나 조건이 많을수록 이해하고 구조를 잡는 데 어려움을 느낀다는 점을 다시 한 번 깨달았다.
앞으로는 문제를 단순히 읽는 데 그치지 않고, 구현 흐름을 머릿속에 명확히 그려보는 연습을 통해 문제 이해력과 구현력을 함께 키워야겠다고 느꼈다.

 

감사합니다.