백준 17144번 미세먼지 안녕! (삼성 SW 역량 테스트 기출 문제) java 풀이

 

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 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 복사

188

미세먼지의 확산이 일어나면 다음과 같은 상태가 된다. 

 

공기청정기가 작동한 이후 상태는 아래와 같다.

 

예제 입력 2 복사

7 8 2
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

예제 출력 2 복사

188

예제 입력 3 복사

7 8 3
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

예제 출력 3 복사

186

예제 입력 4 복사

7 8 4
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

예제 출력 4 복사

178

예제 입력 5 복사

7 8 5
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

예제 출력 5 복사

172

예제 입력 6 복사

7 8 20
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

예제 출력 6 복사

71

예제 입력 7 복사

7 8 30
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

예제 출력 7 복사

52

예제 입력 8 복사

7 8 50
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

예제 출력 8 복사

46

 

 

bfs를 사용한다고 생각했으나 그럴 필요 없이 주변에 미세먼지를 가능한 방향으로 모두 퍼트리고 회전시키면 되었던 문제이다.

문제의 풀이와 미세먼지를 퍼트리는 기능을 만드는 것은 쉬웠으나 회전 시키는 과정이 조금 헷갈려서 시간이 오래걸렸던 문제이다. 그래도 이번에 우테코 프리코스 과정을 거치면서 자바 코드의 변수명과 함수명을 서술적이고 직관적인 이름으로 사용하려고 하니까 알고리즘 문제를 풀 때 굉장히 시간이 단축되고 이해가 쉬운 코드를 작성할 수 있게 되었다. 변수명과 함수명을 직관적으로 짓는 것만으로 이렇게 효과적으로 알고리즘을 풀 수 있게 되었다는 점에 놀라게 되었고 앞으로도 클린 코드에 대해서 더 깊이 있게 공부를 해야겠다는 생각을 하게 되었다.

 

- java 풀이

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

public class Main {

    static int r, c, t;
    static int map[][];
    static int dy[] = {0, 0, -1, 1};
    static int dx[] = {1, -1, 0, 0};
    static List<AirCleaner> airCleaners = new ArrayList<>();

    public static class AirCleaner {
        int y;
        int x;

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

    public static class Dust {
        int y;
        int x;
        int amount;

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


    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());

        map = new int[r][c];

        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == -1) {
                    airCleaners.add(new AirCleaner(i, j));
                }
            }
        }

        while (t-- > 0) {
            spread(findDusts());
            rotate();
        }
        System.out.println(calculateRemainDusts());



    }

    private static int calculateRemainDusts() {
        int remainDusts = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] > 0) {
                    remainDusts += map[i][j];
                }
            }
        }
        return remainDusts;
    }

    //clockwise / 시계방향
    //counterclockwise / 반시계방향
    private static void rotate() {

        rotateClockWise();
        rotateCounterClockWise();
    }


    private static void rotateClockWise() {
        int bottom = airCleaners.get(1).y;

        for (int y = bottom + 1; y < r - 1; y++) {
            map[y][0] = map[y + 1][0];
        }

        for (int x = 0; x < c - 1; x++) {
            map[r - 1][x] = map[r - 1][x + 1];
        }

        for (int y = r - 1; y > bottom; y--) {
            map[y][c - 1] = map[y - 1][c - 1];
        }

        for (int x = c - 1; x > 0; x--) {
            map[bottom][x] = map[bottom][x - 1];
        }

        map[bottom][1] = 0;


    }

    private static void rotateCounterClockWise() {

        int top = airCleaners.get(0).y;

        for (int y = top - 1; y > 0; y--) {
            map[y][0] = map[y - 1][0];
        }

        for (int x = 0; x < c - 1; x++) {
            map[0][x] = map[0][x + 1];
        }

        for (int y = 0; y < top; y++) {
            map[y][c - 1] = map[y + 1][c - 1];
        }

        for (int x = c - 1; x > 0; x--) {
            map[top][x] = map[top][x - 1];
        }

        map[top][1] = 0;


    }

    private static void printMap() {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private static List<Dust> findDusts() {
        List<Dust> dusts = new ArrayList<>();

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] != -1 && map[i][j] != 0) {
                    dusts.add(new Dust(i, j, map[i][j]));
                }
            }
        }

        return dusts;
    }

    private static void spread(List<Dust> dusts) {

        for (int i = 0; i < dusts.size(); i++) {
            int cy = dusts.get(i).y;
            int cx = dusts.get(i).x;
            int amount = dusts.get(i).amount;
            int spreadAmount = amount / 5;
            int spreadDirectionCount = 0;

            for (int j = 0; j < 4; j++) {
                int ny = cy + dy[j];
                int nx = cx + dx[j];
                if (ny >= 0 && nx >= 0 && ny < r && nx < c && map[ny][nx] != -1) {
                    spreadDirectionCount++;
                }
            }

            map[cy][cx] = map[cy][cx] - spreadAmount * spreadDirectionCount;

            for (int j = 0; j < 4; j++) {
                int ny = cy + dy[j];
                int nx = cx + dx[j];
                if (ny >= 0 && nx >= 0 && ny < r && nx < c && map[ny][nx] != -1) {
                    map[ny][nx] += spreadAmount;
                }
            }


        }


    }
}