BOJ : 미세먼지 안녕! - C++

김정욱·2021년 4월 6일
0

Algorithm - 문제

목록 보기
203/249
post-custom-banner

미세먼지 안녕!

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0221 ~ 0331
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int R,C,T;
int board[1005][1005];
int tmp[1005][1005];
vector<pair<int,int>> cleaner;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> R >> C >> T;
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++)
        {
            cin >> board[i][j];
            tmp[i][j] = board[i][j];
            if(board[i][j] == 0) continue;
            else if(board[i][j] == -1)
                cleaner.push_back({i,j});
        }

    while(T--)
    {
        // 1) 미세먼지 확산
        for(int i=0;i<R;i++)
        {
            for(int j=0;j<C;j++)
            {
                auto cur = make_pair(i,j);
                if(board[i][j] == 0 or board[i][j] == -1) continue;
                int spread = board[cur.first][cur.second] / 5;
                for(int dir=0;dir<4;dir++)
                {
                    int ny = cur.first + dy[dir];
                    int nx = cur.second + dx[dir];
                    if(nx<0 or ny<0 or nx>=C or ny>=R) continue;
                    if(board[ny][nx] == -1) continue;
                    tmp[ny][nx] += spread;
                    tmp[cur.first][cur.second] -= spread;
                }
            }
        }
        for(int i=0;i<R;i++)
            for(int j=0;j<C;j++)
                board[i][j] = tmp[i][j];

        // 2) 공기청정기 가동
        /* 반시계 방향 */
        for(int i=cleaner[0].first-1;i>0;i--)
            board[i][0] = board[i-1][0];
        for(int i=0;i<C-1;i++)
            board[0][i] = board[0][i+1];
        for(int i=0;i<cleaner[0].first;i++)
            board[i][C-1] = board[i+1][C-1];
        for(int i=C-1;i>1;i--)
            board[cleaner[0].first][i] = board[cleaner[0].first][i-1];
        board[cleaner[0].first][1] = 0;

        /* 시계 방향 */
        for(int j=cleaner[1].first+1;j<R;j++)
            board[j][0] = board[j+1][0];
        for(int j=0;j<C-1;j++)
            board[R-1][j] = board[R-1][j+1];
        for(int j=R-1;j>cleaner[1].first;j--)
            board[j][C-1] = board[j-1][C-1];
        for(int j=C-1;j>1;j--)
            board[cleaner[1].first][j] = board[cleaner[1].first][j-1];
        board[cleaner[1].first][1] = 0;

        for(int i=0;i<R;i++)
            for(int j=0;j<C;j++)
                tmp[i][j] = board[i][j];
    }
    int ans=0;
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++)
            if(board[i][j] != -1)
                ans += board[i][j];
    cout << ans;
    return 0;
}
  • 로직
    • 미세먼지 확산
      • tmp[][]변경된 값저장하고, spread값board[][]판단
      • 미세먼지 확산 로직 수행
    • 공기청정기 가동
      • 반시계방향 수행
      • 시계방향 수행
    • 변경된 board[][]tmp[][]복사
    • 앞 과정 반복 & 마지막에 Count!
profile
Developer & PhotoGrapher
post-custom-banner

0개의 댓글