BOJ 17144 미세먼지 안녕

작성일 | In |

Problem : 미세먼지 안녕

유형 : 구현

문제 해석

  • T초가 지난 뒤 방 전체의 미세 먼지 양을 구하라.
  • 미세먼지가 퍼진다.
  • 공기청정기가 돈다.

문제 재해석

  • 단순 구현 문제이다.

해결 전략 (15)

  • 공기 청정기는 항상 1열에 있는점을 이용한다.
    • 먼저 등장하는 부분이 앞, 나중에 등장하는 부분이 뒤이다.
  • 미세 먼지를 퍼뜨린다.
    • 미세 먼지가 퍼지는 것은 동시에 일어나므로, 다른 배열에 저장한다.

설계 , 구현 (40)

  • 미세 먼지를 먼저 퍼뜨린다.
  • 미세 먼지를 다 퍼뜨렸으면, 퍼뜨려진 만큼 본래 미세 먼지에 더한다.
  • 공기 청정기는 앞뒤에 따라 공기의 방향이 다르다.
  • 방향 좌표를 시계 방향 순으로 맞춰둔다.
    • 시계 방향 : +1
    • 반 시계 : -1
  • 미세 먼지를 미는 작업은 큐를 이용했다. 사실상 슬라이딩 윈도우 기법을 이용 했다.
    • front는 이전의 공간 상태.
    • 현재 상태를 큐에 넣고, 현재 상태를 이전의 상태로 변경 시킨다.

주의할 점

  • 미세먼지가 동시에 퍼져 나간다.
  • 1x1 의 미세먼지가 퍼져서 2x1에 더해지고, 더해진 2x1 이 퍼지면 안된다.

디버깅 (15)

  • 먼지를 동시에 퍼뜨려야 하는데, 하나씩 퍼뜨리고 작업을 이어나가는 실수를 했다.
  • 미세 먼지 총량을 구하지 않고, 미세 먼지가 있는 공간 개수를 리턴 시키는 실수를 했다.

리팩토링 (20)

  • 초기 코드가 너무 길어서, 처음에는 미세 먼지가 있는 공간 역시 큐로 관리한것을 배열로 바꿔서 다시 구현했다.

코드

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
#define pp pair<int, int>
#define x first
#define y second

using namespace std;

const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int n, m, t;

vector<pp> marchine;
queue<pp> dust_q;

int room[52][52];
int save_dust[52][52];

int Left_Dust() {
    int ret = 0;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            if (room[i][ii] == -1)continue;
            ret += room[i][ii];
        }
    }
    return ret;
}

void Run_Machine() {

    for (int i = 0; i < 2; ++i) {
        queue<int> q;
        q.push(0);

        int dir = 0;
        pp cur = marchine[i];

        while (!q.empty()) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];

            if (nx < 0 or nx >= n or ny < 0 or ny >= m) {
                if (i == 0) dir -= 1;
                else dir += 1;

                if (dir < 0) dir += 4;
                if (dir >= 4) dir %= 4;

                nx = cur.x + dx[dir];
                ny = cur.y + dy[dir];
            }

            if (room[nx][ny] == -1) break;

            q.push(room[nx][ny]);
            room[nx][ny] = q.front();
            cur.x = nx, cur.y = ny;
            q.pop();
        }
    }
}

void Add_Dust() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            room[i][ii] += save_dust[i][ii];
        }
    }
}

void Spread_Dust(const int &i, const int &ii) {

    int cnt = 0;
    int dust_vol = room[i][ii] / 5;

    for (int dir = 0; dir < 4; ++dir) {
        int nx = i + dx[dir];
        int ny = ii + dy[dir];

        if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
        if (room[nx][ny] == -1) continue;
        cnt++;
        save_dust[nx][ny] += dust_vol;
    }

    room[i][ii] -= dust_vol * cnt;
}


void Find_Dust() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            if (room[i][ii] == 0 or room[i][ii] == -1) continue;
            Spread_Dust(i, ii);
        }
    }
}

void Solve() {

    while (t--) {
        memset(save_dust, 0, sizeof(save_dust));
        Find_Dust();
        Add_Dust();
        Run_Machine();
    }
    cout << Left_Dust() << "\n";
}

void Input() {
    cin >> n >> m >> t;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < m; ++ii) {
            cin >> room[i][ii];
            if (room[i][ii] != -1) continue;
            marchine.push_back({ i,ii });
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 구현 속도를 좀 더 올려야겠다.
  • 설계를 다 하고, 설계 내용을 한번 더 곱씹으며 구현하다 보니 오래 걸렸다.