본문 바로가기
알고리즘/Implementation

미세먼지 안-녕!

by 히포파타마스 2022. 7. 8.

미세먼지 안-녕!

백준 17144번 문제.

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

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

 

 

 

 

1. 문제

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

 

[예제 1]

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

 

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

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

 

다음은 확산의 예시이다.

 

[예제 2]

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

 

 

[예제 3]

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

 

 

[예제 4]

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

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

 

 

[예제 5]

방의 정보가 주어졌을 때, 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

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

 

[예제 6]

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

 

 

[예제 7]

 

 

예제 입력 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

 

 

 

 

2. 풀이

■ 문제 풀이

문제의 시뮬레이션은 다음과 같은 절차를 갖는다.

 

1.  미세 먼지 확산

2. 공기 청정기 작동

 

위와 같은 절차를 갖는 시뮬레이션을 실행시키기 위해 다음과 같은 객체를 구현한다.

 

● Dust(미세먼지)

◎ 미세먼지를 객체화한 클래스

◎ 스스로 문제의 조건에 따라 확산할 수 있는 기능(메서드)를 갖고 있다.

 

● AirConditioner(공기청정기)

◎ 공기청정기를 객체화한 클래스

◎ 문제의 조건에 따라 공기를 순환시키는 기능(메서드)를 갖고 있다.

 

위의 객체를 사용해서 다음과 같은 순서로 코드를 진행한다.

 

1. 입력받은 2차 배열의 크기와 미세먼지의 양으로 Dust로 이루어진 2차 배열 dusts을 생성한다.

2. 입력받은 공기청정기의 위치로 AirConditioner을 생성한다.

3. dusts의 모든 Dust에 대해 "확산"기능을 실행

4. "확산"된 미세먼지를 계산

5. AirConditioner의 공기를 순환시키는 메서드를 실행

 

 

 

 

3. Code

■ AirConditioner

공기청정기를 객체화한 클래스

 

[AirConditioner]

public static class AirConditioner {
    Point top;
    Point bottom;

    public AirConditioner() {
    }

    public void setAirConditioner(Point point) {
        if (top == null) {
            this.top = point;
        } else {
            this.bottom = point;
        }
    }

    public void cycle(Dust[][] dusts, int rowSize, int colSize) {

        for (int i = 1; i < this.top.x; i++) {
            dusts[this.top.x - i][0] = dusts[this.top.x - i - 1][0];
        }
        for (int i = 0; i < colSize - 1; i++) {
            dusts[0][i] = dusts[0][i + 1];
        }
        for (int i = 0; i < this.top.x; i++) {
            dusts[i][colSize - 1] = dusts[i + 1][colSize - 1];
        }
        for (int i = 0; i < colSize - 2; i++) {
            dusts[this.top.x][colSize - 1 - i] = dusts[this.top.x][colSize - 2 - i];
        }
        dusts[this.top.x][this.top.y + 1] = new Dust(0);

        int downSize = rowSize - 1 - this.bottom.x;
        for (int i = 1; i < downSize; i++) {
            dusts[this.bottom.x + i][0] = dusts[this.bottom.x + i + 1][0];
        }
        for (int i = 0; i < colSize - 1; i++) {
            dusts[rowSize - 1][i] = dusts[rowSize - 1][i + 1];
        }
        for (int i = 0; i < downSize; i++) {
            dusts[rowSize - 1 - i][colSize - 1] = dusts[rowSize - 2 - i][colSize - 1];
        }
        for (int i = 0; i < colSize - 2; i++) {
            dusts[this.bottom.x][colSize - 1 - i] = dusts[this.bottom.x][colSize - 2 - i];
        }
        dusts[this.bottom.x][this.bottom.y + 1] = new Dust(0);
    }
}

 

 

□ setAirConditioner

AirConditioner의 위치를 초기화하는 메서드

 

[setAirConditioner]

public void setAirConditioner(Point point) {
    if (top == null) {
        this.top = point;
    } else {
        this.bottom = point;
    }
}

AirContitioner은 "위"와 "아래" 두 칸으로 이루어져 있으므로 각각의 인덱스를 받아 초기화해준다.

 

 

□ cycle

주어진 조건에 따라 공기를 순환시키는 메서드

 

[cycle]

public void cycle(Dust[][] dusts, int rowSize, int colSize) {

    for (int i = 1; i < this.top.x; i++) {   //[1]
        dusts[this.top.x - i][0] = dusts[this.top.x - i - 1][0];
    }
    for (int i = 0; i < colSize - 1; i++) {
        dusts[0][i] = dusts[0][i + 1];
    }
    for (int i = 0; i < this.top.x; i++) {
        dusts[i][colSize - 1] = dusts[i + 1][colSize - 1];
    }
    for (int i = 0; i < colSize - 2; i++) {
        dusts[this.top.x][colSize - 1 - i] = dusts[this.top.x][colSize - 2 - i];
    }
    dusts[this.top.x][this.top.y + 1] = new Dust(0);

    int downSize = rowSize - 1 - this.bottom.x;   //[2]
    for (int i = 1; i < downSize; i++) {
        dusts[this.bottom.x + i][0] = dusts[this.bottom.x + i + 1][0];
    }
    for (int i = 0; i < colSize - 1; i++) {
        dusts[rowSize - 1][i] = dusts[rowSize - 1][i + 1];
    }
    for (int i = 0; i < downSize; i++) {
        dusts[rowSize - 1 - i][colSize - 1] = dusts[rowSize - 2 - i][colSize - 1];
    }
    for (int i = 0; i < colSize - 2; i++) {
        dusts[this.bottom.x][colSize - 1 - i] = dusts[this.bottom.x][colSize - 2 - i];
    }
    dusts[this.bottom.x][this.bottom.y + 1] = new Dust(0);
}

● [1] : 공기청정기의 윗부분으로부터 반 시계방향으로 공기를 순환시키는 반복문

             반복문은 시계방향으로 공기청정기에 미세먼지가 사라지는 부분(공기청정기의 윗부분)부터 미세먼지를 한 칸씩 이동시키며 덮었으

             는 방식으로 실행된다.

● [2] : 공기청정기의 아랫부분으로 시계방향으로 공기를 순환시키는 반복문. 반복문은 윗부분과 동일한 논리로 실행된다.

 

 

 

■ Dust

미세먼지를 객체화한 클래스

 

[Dust]

public static class Dust {
    int size;
    int addSize = 0;

    public Dust(int size) {
        this.size = size;
    }

    public void sum() {
        this.size += addSize;
        addSize = 0;
    }

    public void diffusion(Dust[][] dusts, AirConditioner airConditioner,
                          int rowSize, int colSize, int row, int col) {
        int dustSize = this.size;
        for (int k = 0; k < 4; k++) {
            int nextRow = row + rowSet[k];
            int nextCol = col + colSet[k];
            if (nextRow < 0 || nextRow > rowSize - 1 || nextCol < 0 || nextCol > colSize - 1 ||
                    (nextRow == airConditioner.top.x && nextCol == airConditioner.top.y) ||
                    (nextRow == airConditioner.bottom.x && nextCol == airConditioner.bottom.y)) {
                continue;
            }
            dusts[nextRow][nextCol].addSize += dustSize / 5;
            this.size -= dustSize / 5;
        }
    }
}

 

 

□ Field & sum

[Field & sum]

int size;
int addSize = 0;   //[1]

public Dust(int size) {
    this.size = size;
}

public void sum() {   //[2]
    this.size += addSize;
    addSize = 0;
}

● [1] : 확산된 미세먼지를 일시적으로 저장하는 필드

             2차 배열을 순차적으로 순회하며 미세먼지를 확산시키기 때문에 확산된 미세먼지와 본래 미세먼지의 양을 분리시켰다.

● [2] : 확산된 미세먼지를 본래 미세먼지의 양에 더해주는 메서드

 

 

□ diffusion

주어진 조건에 의해 미세먼지를 확산시키는 메서드

 

[diffusion]

public void diffusion(Dust[][] dusts, AirConditioner airConditioner,
                      int rowSize, int colSize, int row, int col) {
    int dustSize = this.size;   //[1]
    for (int k = 0; k < 4; k++) {   //[2]
        int nextRow = row + rowSet[k];
        int nextCol = col + colSet[k];
        if (nextRow < 0 || nextRow > rowSize - 1 || nextCol < 0 || nextCol > colSize - 1 ||
                (nextRow == airConditioner.top.x && nextCol == airConditioner.top.y) ||
                (nextRow == airConditioner.bottom.x && nextCol == airConditioner.bottom.y)) {
            continue;
        }
        dusts[nextRow][nextCol].addSize += dustSize / 5;   //[3]
        this.size -= dustSize / 5;
    }
}

● [1] : 확산되는 먼지의 양은 초기 미세먼지의 양에 의해 결정되기 때문에 초기 미세먼지의 양으로 dustSize를 초기화

● [2] : 상하좌우로 확산. 범위를 벗어나거나 공기청정기가 있는 곳은 확산하지 않는다.

● [3] : 문제의 조건에 따라 확산될 미세먼지의 양을 확산받아지는 미세먼지의 addSize에 더해준다.

 

 

 

■ Simulation Method

시뮬레이션 진행에 관한 메서드

 

[Simulation Method]

public static void simulationDust_Diffusion(Dust[][] dusts, AirConditioner airConditioner, int rowSize, int colSize) {
    for (int i = 0; i < rowSize; i++) {
        for (int j = 0; j < colSize; j++) {
            Dust dust = dusts[i][j];
            if (dust == null || dust.size == 0) {
                continue;
            }
            dust.diffusion(dusts, airConditioner, rowSize, colSize, i, j);
        }
    }
}

public static void simulationDust_Sum(Dust[][] dusts, int rowSize, int colSize) {
    for (int i = 0; i < rowSize; i++) {
        for (int j = 0; j < colSize; j++) {
            Dust dust = dusts[i][j];
            if (dust == null) {
                continue;
            }
            dust.sum();
        }
    }
}

 

 

□ simlationDust_Diffusion

Dust가 저장된 2차 배열을 순회하며 미세먼지의 확산 메서드(diffusion)를 실행시키는 메서드

 

[simlationDust_Diffusion]

public static void simulationDust_Diffusion(Dust[][] dusts, AirConditioner airConditioner, int rowSize, int colSize) {
    for (int i = 0; i < rowSize; i++) {
        for (int j = 0; j < colSize; j++) {
            Dust dust = dusts[i][j];
            if (dust == null || dust.size == 0) {   //[1]
                continue;
            }
            dust.diffusion(dusts, airConditioner, rowSize, colSize, i, j);
        }
    }
}

● [1] : 미세먼지가 null(공기청정기)이거나 미세먼지의 양이 0인 경우는 넘어간다.

 

 

□ simulationDust_Sum

Dust가 저장된 2차배열을 순회하면 Dust의 미세먼지 양에 확산된 미세먼지를 더해주(sum)는 메서드를 실행하는 메서드

 

[simulationDust_Sum]

public static void simulationDust_Sum(Dust[][] dusts, int rowSize, int colSize) {
    for (int i = 0; i < rowSize; i++) {
        for (int j = 0; j < colSize; j++) {
            Dust dust = dusts[i][j];
            if (dust == null) {   //[1]
                continue;
            }
            dust.sum();
        }
    }
}

● [1] : Dust가 null(공기청정기 위치)일 경우 반복문을 넘긴다.

 

 

 

■ main

[main]

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int rowSize = scanner.nextInt();
    int colSize = scanner.nextInt();
    int totalTime = scanner.nextInt();

    AirConditioner airConditioner = new AirConditioner();
    Dust[][] dusts = new Dust[rowSize][colSize];

    for (int i = 0; i < rowSize; i++) {   //[1]
        for (int j = 0; j < colSize; j++) {
            int dustSize = scanner.nextInt();
            if (dustSize == -1) {   //[2]
                airConditioner.setAirConditioner(new Point(i, j));
                continue;
            }
            dusts[i][j] = new Dust(dustSize);
        }
    }

    for (int i = 0; i < totalTime; i++) {   //[3]
        simulationDust_Diffusion(dusts, airConditioner, rowSize, colSize);
        simulationDust_Sum(dusts, rowSize, colSize);
        airConditioner.cycle(dusts, rowSize, colSize);
    }

    int result = Arrays.stream(dusts)   //[4]
            .flatMap(Arrays::stream)
            .filter(Objects::nonNull)
            .mapToInt(dust -> dust.size).sum();

    System.out.println(result);
}

● [1] : 입력받은 미세먼지의 양으로 2차 배열에 Dust를 초기화해준다.

● [2] : 입력받은 미세먼지의 양이 -1일 경우(=공기청정기를 의미) 해당 위치로 AirConditioner의 필드를 초기화해준다.

● [3] : 주어진 시간 동안 시뮬레이션을 진행(확산 -> 확산된 미세먼지 합산 -> 공기 순환).

● [4] : null을 제외한 dusts의 미세먼지 양의 합을 구한다.

 

 

 

■ 전체 코드

[전체 코드]

import java.awt.*;
import java.util.Arrays;
import java.util.Objects;
import java.util.Scanner;

/*
백준 17144번 문제
https://www.acmicpc.net/problem/17144
*/

public class Main {

    static int[] rowSet = {-1, 0, 1, 0};
    static int[] colSet = {0, 1, 0, -1};

    public static class AirConditioner {
        Point top;
        Point bottom;

        public AirConditioner() {
        }

        public void setAirConditioner(Point point) {
            if (top == null) {
                this.top = point;
            } else {
                this.bottom = point;
            }
        }

        public void cycle(Dust[][] dusts, int rowSize, int colSize) {

            for (int i = 1; i < this.top.x; i++) {
                dusts[this.top.x - i][0] = dusts[this.top.x - i - 1][0];
            }
            for (int i = 0; i < colSize - 1; i++) {
                dusts[0][i] = dusts[0][i + 1];
            }
            for (int i = 0; i < this.top.x; i++) {
                dusts[i][colSize - 1] = dusts[i + 1][colSize - 1];
            }
            for (int i = 0; i < colSize - 2; i++) {
                dusts[this.top.x][colSize - 1 - i] = dusts[this.top.x][colSize - 2 - i];
            }
            dusts[this.top.x][this.top.y + 1] = new Dust(0);

            int downSize = rowSize - 1 - this.bottom.x;
            for (int i = 1; i < downSize; i++) {
                dusts[this.bottom.x + i][0] = dusts[this.bottom.x + i + 1][0];
            }
            for (int i = 0; i < colSize - 1; i++) {
                dusts[rowSize - 1][i] = dusts[rowSize - 1][i + 1];
            }
            for (int i = 0; i < downSize; i++) {
                dusts[rowSize - 1 - i][colSize - 1] = dusts[rowSize - 2 - i][colSize - 1];
            }
            for (int i = 0; i < colSize - 2; i++) {
                dusts[this.bottom.x][colSize - 1 - i] = dusts[this.bottom.x][colSize - 2 - i];
            }
            dusts[this.bottom.x][this.bottom.y + 1] = new Dust(0);
        }
    }

    public static class Dust {
        int size;
        int addSize = 0;

        public Dust(int size) {
            this.size = size;
        }

        public void sum() {
            this.size += addSize;
            addSize = 0;
        }

        public void diffusion(Dust[][] dusts, AirConditioner airConditioner,
                              int rowSize, int colSize, int row, int col) {
            int dustSize = this.size;
            for (int k = 0; k < 4; k++) {
                int nextRow = row + rowSet[k];
                int nextCol = col + colSet[k];
                if (nextRow < 0 || nextRow > rowSize - 1 || nextCol < 0 || nextCol > colSize - 1 ||
                        (nextRow == airConditioner.top.x && nextCol == airConditioner.top.y) ||
                        (nextRow == airConditioner.bottom.x && nextCol == airConditioner.bottom.y)) {
                    continue;
                }
                dusts[nextRow][nextCol].addSize += dustSize / 5;
                this.size -= dustSize / 5;
            }
        }
    }

    public static void simulationDust_Diffusion(Dust[][] dusts, AirConditioner airConditioner, int rowSize, int colSize) {
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                Dust dust = dusts[i][j];
                if (dust == null || dust.size == 0) {
                    continue;
                }
                dust.diffusion(dusts, airConditioner, rowSize, colSize, i, j);
            }
        }
    }

    public static void simulationDust_Sum(Dust[][] dusts, int rowSize, int colSize) {
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                Dust dust = dusts[i][j];
                if (dust == null) {
                    continue;
                }
                dust.sum();
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int rowSize = scanner.nextInt();
        int colSize = scanner.nextInt();
        int totalTime = scanner.nextInt();

        AirConditioner airConditioner = new AirConditioner();
        Dust[][] dusts = new Dust[rowSize][colSize];

        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                int dustSize = scanner.nextInt();
                if (dustSize == -1) {
                    airConditioner.setAirConditioner(new Point(i, j));
                    continue;
                }
                dusts[i][j] = new Dust(dustSize);
            }
        }

        for (int i = 0; i < totalTime; i++) {
            simulationDust_Diffusion(dusts, airConditioner, rowSize, colSize);
            simulationDust_Sum(dusts, rowSize, colSize);
            airConditioner.cycle(dusts, rowSize, colSize);
        }

        int result = Arrays.stream(dusts)
                .flatMap(Arrays::stream)
                .filter(Objects::nonNull)
                .mapToInt(dust -> dust.size).sum();

        System.out.println(result);
    }
}

 

 

 

저작자표시

'알고리즘 > Implementation' 카테고리의 다른 글

정육면체 전개-도  (0) 2022.08.09
A-C  (0) 2022.05.15

관련글

댓글

티스토리툴바