[Algorithm/C++17] 백준 17144 미세먼지 안녕!

문제

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

17144번: 미세먼지 안녕!

풀이 방법

1초동안 미세먼지 확산, 공기청정기 작동이 일어나며 T초 후 미세먼지의 양을 구하는 구현, 시뮬레이션 문제다.

주의할 점은

• 미세먼지가 확산 될 때는 그 시간의 미세먼지 양에 대해서만 처리를 해야한다. 다시말해, 확산될 때 제 자리와 확산된 방향의 A(r,c)이 변하게 되는데, 변한 값으로 확산을 처리하면 안된다. 문제에서 확산의 예시 세번째를 보면 이해가 될 것이다. 아래 코드에서는 이를 위해 미세먼지의 좌표 및 양을 tuple로 저장해주었다.
• 미세먼지의 양이 5 미만인 경우 확산되지 않고 이동만 한다.
• 공기청정기의 반시계, 시계방향 순회 구현이 좀 까다로울 수 있다.

이 점들만 주의하면 풀 수 있다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
int dy[] = {-1,1,0,0};
int dx[] = {0,0,-1,1};
int main()
{
    int R, C, T;
    scanf("%d %d %d", &R, &C, &T);
    vector<vector<int>> v(R, vector<int>(C));
    vector<pair<int,int>> cleaner;
    queue<tuple<int,int,int>> dust;
    for(int i=0; i<R; i++)
    {
        for(int j=0; j<C; j++)
        {
            scanf("%d", &v[i][j]);
            if(v[i][j] == -1)
                cleaner.push_back({i,j});
            if(v[i][j] >= 5)
                dust.push({i,j,v[i][j]});
                
        }
    }
    
    while(T--)
    {
	    // 미세먼지 확산
	    int qsize = dust.size();
	    for(int i=0; i<qsize; i++)
	    {
	        auto cur = dust.front();
	        int y = get<0>(cur);
	        int x = get<1>(cur);
	        int amount = get<2>(cur);
	        dust.pop();
	
	        int count = 0;
	        for(int i=0; i<4; i++)
	        {
	            int ny = y + dy[i];
	            int nx = x + dx[i];
	            if(ny < 0 || ny >= R || nx < 0 || nx >= C)
	                continue;
	            if(v[ny][nx] == -1)
	                continue;
	            
	            count++;
	            v[ny][nx] += amount/5;
	        }
	        v[y][x] = v[y][x] - amount/5 * count;
	    }
    	// 공기청정기 작동
        auto upper = cleaner[0];
        // 반시계
        for(int y=upper.first-1; y>0; y--)
        {
            v[y][upper.second] = v[y-1][upper.second];
        }
        for(int x=0; x<C-1; x++)
        {
            v[0][x] = v[0][x+1];
        }
        for(int y=0; y<upper.first; y++)
        {
            v[y][C-1] = v[y+1][C-1];
        }    
        for(int x=C-1; x>upper.second+1; x--)
        {
            v[upper.first][x] = v[upper.first][x-1];
        }
        v[upper.first][1] = 0;
        
        // 시계 방향
        auto lower = cleaner[1];
        for(int y=lower.first+1; y<R-1; y++)
        {
            v[y][lower.second] = v[y+1][lower.second];
        }
        for(int x=0; x<C-1; x++)
        {
            v[R-1][x] = v[R-1][x+1];
        }
        for(int y=R-1; y>lower.first; y--)
        {
            v[y][C-1] = v[y-1][C-1];
        }    
        for(int x=C-1; x>lower.second+1; x--)
        {
            v[lower.first][x] = v[lower.first][x-1];
        }
        v[lower.first][1] = 0;
        
        // 다음에 확산할 미세먼지 저장
	    for(int i=0; i<R; i++)
	    {
	    	for(int j=0; j<C; j++)
	    	{
	    		if(v[i][j] >= 5)
	    			dust.push({i,j,v[i][j]});
	    	}
	    }
	    /*
        // 테스트 출력
    	printf("\n");
        for(int i=0; i<R; i++)
        {
        	for(int j=0; j<C; j++)
        	{
        		printf("%3d", v[i][j]);
        	}
        	printf("\n");
        }
        */
    }
    // 정답 계산
    int answer = 2;
    for(int i=0; i<R; i++)
    {
    	for(int j=0; j<C; j++)
    	{
    		answer += v[i][j];
    	}
    }
    printf("%d\n", answer);
    
    return 0;
}

고찰