Algorithm 문제

[백준] 17144 - 미세먼지 안녕!

노예2 2019. 7. 8. 17:00

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

 

17144번: 미세먼지 안녕!

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

www.acmicpc.net

 

알고리즘적으로는 간단한 구현 문제.

 

주의할 점이 있다면, 먼지 확산이 동시에 일어나기 때문에, 각 칸에 확산되는 먼지는 모든 칸에서 계산이 끝난 뒤에 적용되어야 한다.

공기 청정기 부분은 4 방향에 대해서 각각 반복문을 작성하였다. 각 방향의 시작, 끝 인덱스를 정확히 결정해야 한다.

 

<C++ 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
 
int main(){
    int r, c, t;
    int room[51][51];
    int cl;
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    scanf("%d %d %d", &r, &c, &t);
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            scanf("%d", &room[i][j]);
            if(room[i][j] == -1){
                cl = i;
            }
        }
    }
    cl--;
 
    for(int time=0; time<t; time++){
        // 확산
        // 이동되는 먼지 양 계산
        int exp[51][51] = {};
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                if(room[i][j] != 0 && room[i][j] != -1){
                    int cnt = 0;
                    for(int k=0; k<4; k++){
                        int ay = i + dy[k], ax = j + dx[k];
                        if(ay >= 0 && ay < r && ax >= 0 && ax < c && room[ay][ax] != -1){
                            cnt++;
                            exp[ay][ax] += room[i][j] / 5;
                        }
                    }
                    room[i][j] -= (room[i][j] / 5) * cnt;
                }
            }
        }
        // 먼지 이동 적용
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                room[i][j] += exp[i][j];
            }
        }
 
        // 순환
        // 삭제되는 부분부터 제거해야 다른 항이 소실되지 않음
 
        // 윗방향 순환
        // 위에서 아래 방향으로
        for(int i=cl-1; i>=1; i--){
            room[i][0] = room[i-1][0];
        }
        // 우측에서 좌측으로
        for(int i=0; i<c-1; i++){
            room[0][i] = room[0][i+1];
        }
        // 아래에서 위
        for(int i=0; i<cl; i++){
            room[i][c-1] = room[i+1][c-1];
        }
        // 좌에서 우
        for(int i=c-1; i>=1; i--){
            room[cl][i] = room[cl][i-1];
        }
        // 정화 공기로 채워진 장소
        room[cl][1] = 0;
 
 
        // 아래방향 순환
        // 아래에서 위 방향으로
        for(int i=cl+2; i<r-1; i++){
            room[i][0] = room[i+1][0];
        }
        // 좌측에서 우측으로
        for(int i=0; i<c-1; i++){
            room[r-1][i] = room[r-1][i+1];
        }
        // 위에서 아래
        for(int i=r-1; i>cl+1; i--){
            room[i][c-1] = room[i-1][c-1];
        }
        // 좌에서 우
        for(int i=c-1; i>=1; i--){
            room[cl+1][i] = room[cl+1][i-1];
        }
        // 정화 공기로 채워진 장소
        room[cl+1][1] = 0;
    }
 
    int sum = 2; // 공기 청정기 2
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            sum += room[i][j];
        }
    }
    printf("%d", sum);
 
    return 0;
}
cs