자바 - 백준 17144 / 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

골드 4

 

구현 방법

구현 문제라서 문제부터 간단하게 요약했다.

plate -> r * c
공기청정기 = 1번열(c) 설치, 두행(r) 차지한다
미세먼지 양 = A(r, c)

<1초 동안 일어나는 일>
a.
미세먼지 모든칸 동시에 확산, 네방향으로
인접한 방향에 공기청정기 있거나 칸없으면 확산 x
확산 양  : a(r,c) / 5 소수점 버리기
(r,c)에 남은 양 : a(r, c) - a(r,c)/5 * (확산 방향 개수)

b.
공기청정기 바람 나옴
위 : 반시계방향 순환
아래 : 시계방향 순환
바람 불면 => 미세먼지가 바람의 방향대로 한칸씩 이동
미세먼지 공기청정기로 들어가면 정화됨

 

조건

 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000)

 

구현 방식은 초당[O(N)] 이차원 배열[O(N^2)]을 모두 돌면서 미세먼지를 확인 할 예정이다. 이경우 시간 복잡도가 O(N^3)이 걸리지만 조건에 의해서 계산해보면 1,000 * 50 * 50으로 1,500,000이 되기 때문에 런타임 에러는 걱정 안해도 된다.

 

1초에 미세먼지의 확산이 동시에 일어나기 때문에 확산에 의한 미세먼지 변경 이차원 배열(tempPlate)을 따로 하나 더 생성한다. 그 후에 기존의 미세먼지 정보가 있는 이차원 배열(plate)을 통해 업데이트 정보를 tempPlate에 기록하고, 공기 청전기까지 모두 완료 후(==1초가 끝나는 시점), plate에 tempPlate 정보를 업데이트 하는 방식으로 구현 하였다.

 

이때 주의할 점은 tempPlate에 plate의 미세먼지 정보를 그냥 대입하면 안된다(tempPlate = plate 이렇게 하면 안된다).

이유는 tempPlate에 있는 미세먼지 정보들은 확산에 의해 정보가 계속 변하고 있다는 점 때문이다. tempPlate = plate 이렇게 해버리면 다른 미세먼지에 의해 확산된 미세먼지 정보가 무시된다. 그러므로 tempPlate += plate 이렇게 해야 한다. 

코드

package boj;

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

/**
 * 백준 17144
 * 미세먼지 안녕!
 * 골드4
 * https://www.acmicpc.net/problem/17144
 */
public class Boj17144 {

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

        //r 행, c 열, t 초
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

        int[][] plate = new int[r][c];
        //공기 청정기 위치 int[0] = 행, int[1] = 열
        ArrayList <int[]> airFresh = new ArrayList<>();

        for(int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < c; j++) {
                int cur = Integer.parseInt(st.nextToken());
                plate[i][j] = cur;

                if(cur == -1)
                    airFresh.add(new int[] {i, j});
            }
        }

        for(int time = 0; time < t; time++) {
            int[][] tempPlate = new int[r][c];

            //미세먼지 확산
            for(int i = 0; i < r; i++) {

                for(int j = 0; j < c; j++) {
                    if(plate[i][j] == -1) {
                        tempPlate[i][j] = -1;
                        continue;
                    }

                    if(plate[i][j] > 0) {

                        tempPlate[i][j] += plate[i][j];
                        int temp = diffuseValue(plate[i][j]);

                        //상
                        if(i - 1 >= 0 && plate[i - 1][j] != -1) {
                            tempPlate[i][j] -= temp;
                            tempPlate[i - 1][j] += temp;
                        }

                        //하
                        if(i + 1 < r && plate[i + 1][j] != -1) {
                            tempPlate[i][j] -= temp;
                            tempPlate[i + 1][j] += temp;
                        }

                        //좌
                        if(j - 1 >= 0 && plate[i][j - 1] != -1) {
                            tempPlate[i][j] -= temp;
                            tempPlate[i][j - 1] += temp;
                        }

                        //우
                        if(j + 1 < c && plate[i][j + 1] != -1) {
                            tempPlate[i][j] -= temp;
                            tempPlate[i][j + 1] += temp;
                        }
                    }

                }
            }

            //반시계 공기 청정기 작동
            turnCounterClock(tempPlate, airFresh.get(0)[0], c);

            //시계 공기 청정기 작동
            turnClock(tempPlate, airFresh.get(1)[0], r, c);


            //미세먼지 업데이트
            plate = tempPlate;
        }

        System.out.println(totalDust(plate));
    }

    public static int diffuseValue(int a) {
        return a / 5;
    }

    //반시계 방향
    public static void turnCounterClock(int[][] tempPlate, int airFreshRow, int c ) {
        int startRow = 0;
        int endRow = airFreshRow;
        int startCol = 0;
        int endCol = c;

        for(int i = endRow - 1; i > 0; i--) {
            tempPlate[i][startCol] = tempPlate[i - 1][startCol];
        }

        for(int i = startCol; i < endCol - 1; i++) {
            tempPlate[startRow][i] = tempPlate[startRow][i + 1];
        }

        for(int i = startRow; i < endRow; i++) {
            tempPlate[i][endCol - 1] = tempPlate[i + 1][endCol - 1];
        }

        for(int i = endCol - 1; i > 0; i--) {
            tempPlate[endRow][i] = tempPlate[endRow][i - 1];
        }

        tempPlate[endRow][1] = 0;

    }

    //시계 방향
    public static void turnClock(int[][] tempPlate, int airFreshRow, int r, int c ) {
        int startRow = airFreshRow;
        int endRow = r;
        int startCol = 0;
        int endCol = c;

        for(int i = startRow + 1; i < endRow - 1; i++)
            tempPlate[i][startCol] = tempPlate[i + 1][startCol];

        for(int i = 0; i < endCol - 1; i++)
            tempPlate[endRow - 1][i] = tempPlate[endRow -1][i + 1];

        for (int i = endRow - 1; i > startRow; i--) {
            tempPlate[i][endCol - 1] = tempPlate[i - 1][endCol - 1];
        }

        for(int i = endCol - 1; i > 0; i--)
            tempPlate[startRow][i] = tempPlate[startRow][i - 1];

        tempPlate[startRow][1] = 0;
    }

    public static int totalDust(int[][] plate) {
        int sum = 0;

        for(int i = 0; i < plate.length; i++) {
            for(int j = 0; j < plate[0].length; j++) {
                sum += plate[i][j];
            }

        }

        return sum + 2;
    }
}

느낀 점

이번 구현 문제는 별다른 알고리즘이 필요하지는 않았지만, 고려해야 할 점이 많았다. 또한 구현 과정에서 오류를 잡느라 디버깅 시간이 많이 걸려서 문제를 푸는데 오랜 시간이 걸렸다. 빠르고 정확하게 푸는 연습이 필요하다고 느꼈다.