[백준] 17144번: 미세먼지 안녕! (C++)

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

구현이 조금 까다로워서 시간이 조금 걸렸다.

공기 순환 방향인 up, down 배열을 선언했다.

 

up : {오른쪽, 위, 왼쪽, 아래}

down : {오른쪽, 아래, 왼쪽, 위}

 

1. 미세먼지 확산

• 미세먼지가 있는 좌표와 확산되기 전 먼지 값(origin)을 큐에 넣는다. 
• 확산 가능한 곳이면 origin/5을 더하고, 확산시킨 먼지 값을 origin/5 만큼 빼준다.

2. 공기청정기 작동

• 청정기 (위, 아래)
  • 임시 변수 tmp2에 현재 좌표의 값을 넣는다.
  • 현재 좌표는 tmp1(초기값 0)으로 갱신.
  • tmp1에 tmp2를 넣는다.
  • 다음 좌표 nx, ny가 범위 밖을 벗어나면 up과 down 배열의  index를 증가시킨다.
  • 현재 좌표를 갱신한다.

1, 2 과정을 t번 반복한다.

 

3. 먼지값을 모두 더하고 출력

 

 

소스코드

#include <bits/stdc++.h>
using namespace std;

int r, c, t, result;
int g[51][51];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0 ,0};
int up[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
int down[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<int> v; // 위 : v[0], 아래 : v[1]
queue<pair<pair<int, int>, int> > q; // (미세 먼지 좌표, 원래 먼지값)

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> r >> c >> t;
    for (int i = 1 ; i <= r; i++) {
        for (int j = 1 ; j <= c; j++) {
            cin >> g[i][j];
            if (g[i][j] == -1)
                v.push_back(i);
        }
    }
    while (t--) {
        // 미세먼지를 큐에 넣고
        for (int i = 1 ; i <= r; i++) {
            for (int j = 1 ; j <= c; j++) {
                if (g[i][j] > 0)
                    q.push(make_pair(make_pair(i, j), g[i][j]));
            }
        }
        // 미세먼지 확산
        while (!q.empty()) {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int origin = q.front().second;
            q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if (nx <= 0 || nx > r || ny <= 0 || ny > c || g[nx][ny] == -1) continue; 
                g[nx][ny] += origin / 5;
                g[x][y] -= origin / 5;
            }
        }
        // 공기청정기 작동
        int x = v[0], y = 2; // 청정기 위쪽 시작 좌표
        int tmp1 = 0, tmp2 = 0;
        int i = 0;
        while (g[x][y] != -1) {
            // cout << "좌표 : " << x  << ", " << y << '\n';
            tmp2 = g[x][y];
            g[x][y] = tmp1;
            tmp1 = tmp2;

            int nx = x + up[i][0];
            int ny = y + up[i][1];
            if (ny > c || nx < 1 || ny < 1) i++;
            x += up[i][0];
            y += up[i][1];
            
        }

        x = v[1], y = 2; // 청정기 아래쪽 시작 좌표 
        tmp1 = 0, tmp2 = 0, i = 0;
        while (g[x][y] != -1) {
            tmp2 = g[x][y];
            g[x][y] = tmp1;
            tmp1 = tmp2;

            int nx = x + down[i][0];
            int ny = y + down[i][1];
            if (ny > c || nx > r || ny < 1) i++;
            x += down[i][0];
            y += down[i][1];
        }
    }

    for (int i = 1 ; i <= r; i++) {
        for (int j = 1 ; j <= c; j++) {
            if (g[i][j] >0 ) result += g[i][j];
        }
    }

    cout << result;
    return 0;
}