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

문제

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

---

풀이(34분)

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

public class Main {
    static int r, c, t;
    static int[][] arr;
    static Point upPoint, downPoint;
    static int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        arr = new int[r][c];

        int cnt = 1;
        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());
                if (arr[i][j] == -1) {
                    if (cnt == 1) {
                        upPoint = new Point(i, j);
                        cnt++;
                    } else {
                        downPoint = new Point(i, j);
                    }
                }
            }
        }

        for (int i = 0; i < t; i++) {
            arr = diffusion();
            airPurifier();
        }

        int answer = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] > 0) {
                    answer += arr[i][j];
                }
            }
        }

        System.out.println(answer);
    }

    public static void airPurifier() {
        upPurifier();
        downPurifier();
        // 공기청정기 위치는 항상 -1로 설정
        arr[upPoint.x][upPoint.y] = -1;
        arr[downPoint.x][downPoint.y] = -1;
    }

    public static void upPurifier() {
        int x = upPoint.x;

        // 위쪽 공기청정기: 반시계 방향
        for (int i = x - 1; i > 0; i--) arr[i][0] = arr[i - 1][0];  // 아래로 이동
        for (int i = 0; i < c - 1; i++) arr[0][i] = arr[0][i + 1];  // 왼쪽으로 이동
        for (int i = 0; i < x; i++) arr[i][c - 1] = arr[i + 1][c - 1];  // 위로 이동
        for (int i = c - 1; i > 1; i--) arr[x][i] = arr[x][i - 1];  // 오른쪽으로 이동

        arr[x][1] = 0; // 공기청정기 옆
    }

    public static void downPurifier() {
        int x = downPoint.x;

        // 아래쪽 공기청정기: 시계 방향
        for (int i = x + 1; i < r - 1; i++) arr[i][0] = arr[i + 1][0];  // 위로 이동
        for (int i = 0; i < c - 1; i++) arr[r - 1][i] = arr[r - 1][i + 1];  // 왼쪽으로 이동
        for (int i = r - 1; i > x; i--) arr[i][c - 1] = arr[i - 1][c - 1];  // 아래로 이동
        for (int i = c - 1; i > 1; i--) arr[x][i] = arr[x][i - 1];  // 오른쪽으로 이동

        arr[x][1] = 0; // 공기청정기 옆
    }

    public static int[][] diffusion() {
        int[][] tempArr = new int[r][c];

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] > 0) {
                    int origin = arr[i][j];
                    int diffusionDust = origin / 5;

                    for (int k = 0; k < 4; k++) {
                        int tempR = i + direction[k][0];
                        int tempC = j + direction[k][1];

                        if (tempR >= 0 && tempR < r && tempC >= 0 && tempC < c && arr[tempR][tempC] != -1) {
                            tempArr[tempR][tempC] += diffusionDust;
                            origin -= diffusionDust;
                        }
                    }
                    tempArr[i][j] += origin;
                }
            }
        }

        return tempArr;
    }

    public static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

별다른 알고리즘을 사용하지 않는 빡구현 문제라고 생각한다.

 

문제 설명과 풀이가 모두 간단하지만 실제 풀이는 생각보다 단순하다.

 

1. 확산을 먼저 진행한다.

이때 원본 배열을 둔 채로 임시 배열을 두어 원본 배열에 영향을 끼치지 않고 확산을 진행한 뒤에 다시 복사해서 넣는다. -> 이렇게 하는 이유는 한 칸씩 순서대로 확산을 진행할 경우, 이미 확산된 것이 영향을 끼칠 수 있기 때문이다.

1-1. 확산을 진행할 때 벽과 공기 청정기 등 진행이 되지 못하는 것을 고려하여 확산을 진행한다. 

 

2. 윗 순환과 아랫 순환을 별도로 메서드로 분리하여 진행한다.

2-1. 공기 청정기로 들어오는 것부터 생각하여 순서에 맞게 옮겨가며 0을 대입시켜 마무리해 준다.

 

3. 최종적으로 값을 측정한다.

 

말 그대로 구현 문제이다 보니 풀이가 어렵다기보다는 직접 코드로 작성하며 인덱스와 반복문 등을 맞추는 작업이 더욱 어려운 것 같다!