[BOJ] 미세먼지 안녕!(17144)

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

문제 : BOJ_17144번 미세먼지 안녕!

문제 설명

완전탐색, bfs

크기가 R*C인 격자판에서 미세먼지가 4방향으로 확장된 뒤, 확장된 이후에 공기청정기에 의해 위쪽은 반시계, 아래쪽은 시계방향으로 미세먼지들이 돌아갑니다.

이 때 공기청정기에 들어간 미세먼지는 사라집니다.

---

Solution

R과 C의 최댓값이 50, T의 최댓값이 1000이기 때문에, 50501,000=2,500,000임으로 완전탐색이 가능합니다.

미세먼지의 위치와 값을 queue에 다 넣어주고 4방향에 퍼트리는 bfs를 한 뒤, 단순 for문으로 반시계와 시계방향으로 돌리는 방법으로 풀었습니다.

---

Description

1. queue에 해당 위치의 값, 행, 열의 데이터를 넣기위해 pair를 이중으로 사용했습니다.
2. 공기청정기의 값은 -1이므로, 마지막 sum에 2를 더해줍니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int R, C, T;
int map[51][51];
int st, ed;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main(void) {
    scanf("%d%d%d", &R, &C, &T);
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == -1) {
                if (st == 0) st = i;
                else ed = i;
            }
        }
    }
    while (T--) {
        queue<pair<int, pair<int, int>>> q; // q.push({값,{행,열}});
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                if (map[i][j] > 0) q.push({ map[i][j],{ i,j } });
            }
        }
        while (!q.empty()) {
            int x = q.front().second.first;
            int y = q.front().second.second;
            int now_val = q.front().first;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (map[nx][ny] == -1) continue;
                if (nx > R || ny > C || nx < 1 || ny < 1) continue;
                map[nx][ny] += now_val / 5;
                map[x][y] -= now_val / 5;
            }
        }
        // 반시계, 시계방향으로 돌리기 위한 단순 포문
        for (int i = st - 1; i >= 2; i--) map[i][1] = map[i - 1][1];
        for (int i = 1; i < C; i++) map[1][i] = map[1][i + 1];
        for (int i = 1; i < st; i++) map[i][C] = map[i + 1][C];
        for (int i = C; i > 2; i--) map[st][i] = map[st][i - 1];
        map[st][2] = 0;
        for (int i = ed + 1; i < R; i++) map[i][1] = map[i + 1][1];
        for (int i = 1; i < C; i++) map[R][i] = map[R][i + 1];
        for (int i = R; i > ed; i--) map[i][C] = map[i - 1][C];
        for (int i = C; i > 2; i--) map[ed][i] = map[ed][i - 1];
        map[ed][2] = 0;
    }
    int sum = 0;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            sum += map[i][j];
        }
    }
    printf("%d\n", sum + 2);
    // 공기청정기의 값은 -1이므로, 마지막에 2를 더해준다.
}