[BOJ] 미세먼지 안녕!_17144 C++ 풀이

문제

R x C 크기의 집이 존재하고 1번 열에 공기청정기가 위치하고 있다. 1초 동안 아래의 과정이 순서대로 반복된다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

공기청정기의 바람은 다음과 같은 방향으로 순회한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

접근 방법

문제에서 요구하는 바를 그대로 구현하면 되는 문제이지만 신경써야 하는 부분이 많은 문제였다.

이 문제에서 주의해야 할 점은 먼지확산이 이루어 지는 map 배열과 기존의 먼지들이 위치해 있는 배열이 두개 존재해야 한다는 것인데, 먼지가 존재하는 위치를 저장하는 큐를 사용하여 먼지의 확산을 구현하였다.

for(int i=0; i<r; i++)
	for(int j=0; j<c; j++)
	{
		if(map[i][j] != 0 && map[i][j] != -1)
		{
			COORD dirt;
			dirt.y = i;
			dirt.x = j;
			dirt.value = map[i][j];
			prevMap.push(dirt); // 먼지의 위치와 값들을 임시로 prevMap 큐에 저장 (확산을 위해)
		}
	}

공기청정기 바람에 의한 먼지의 순회는 공기청정기의 상단 $($반시계방향), 하단 $($시계방향)으로 나눠서 왼쪽, 상단, 오른쪽, 하단 순으로 for 반복문으로 구현해 주었다.

처음에는 똑같은 map2 라는 배열을 선언하여 map의 값을 그대로 복사할까 생각하였지만 큐를 사용하는 더 적합한 방법을 생각해 낼 수 있었다.

또한 처음에 cleaner 배열을 vector$<$COORD> cleaner(2); 로 선언하는 실수를 범하였다. cleaner(2)를 통해 cleaner 배열의 크기를 2로 동적할당 하고 새로운 값을 push_back 해주면 배열의 크기는 2로 유지한체 push_back 된 새로운 값이 인덱스 0, 1에 초기화 된다고 착각하였던 것이다. 실제로는 cleaner{ {0,0}, {0,0} } 에 추가로 새로운 값이 push_back에 의해 삽입되며 배열의 크기가 커지고 있던 것이었다.

구현

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

typedef struct
{
	int y, x;
	int value;
} COORD;

typedef struct
{
	int y, x;
} D;

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);
	int map[51][51];
	int r, c, t; //행, 열, 시간
	vector<COORD> cleaner; // 공기청정기의 위치를 저장하는 배열
	queue<COORD> prevMap; // 먼지확산을 위해 임시로 먼지의 위치를 저장하는 큐
	D dir[4] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} }; // 상하좌우
	int sum=0;

	cin>>r>>c>>t;

	for(int i=0; i<r; i++)
		for(int j=0; j<c; j++)
		{
			cin>>map[i][j];
			if(map[i][j] == -1)
			{
				COORD air;
				air.y = i;
				air.x = j;
				air.value = -1;
				cleaner.push_back(air); // 공기청정기의 위치를 저장
			}
		}
    
	while(t--)
	{
		for(int i=0; i<r; i++)
			for(int j=0; j<c; j++)
			{
				if(map[i][j] != 0 && map[i][j] != -1)
				{
					COORD dirt;
					dirt.y = i;
					dirt.x = j;
					dirt.value = map[i][j];
					prevMap.push(dirt); // 먼지의 위치와 값들을 임시로 prevMap 큐에 저장 (확산을 위해)
				}
			}
		
		// 먼지 확산 과정
		while(!prevMap.empty())
		{
			int num = 0; // 미세먼지가 확산된 방향의 수를 세는 변수
			int X = prevMap.front().x;
			int Y = prevMap.front().y;
			int val = prevMap.front().value;
			prevMap.pop();

			for(int i=0; i<4; i++)
			{
				int ny = Y + dir[i].y;
				int nx = X + dir[i].x;

				if(0 <= ny && ny < r && 0 <= nx && nx < c)
				{
					if(map[ny][nx] == -1) continue;
					map[ny][nx] += val / 5;
					num++;
				}
			}
			map[Y][X] -= (val/5) * num;
		}

		COORD upper, lower;
		upper = cleaner[0]; lower = cleaner[1];
		//공기 청정기 바람
		// 공기 청정기 상단의 바람 (반시계 방향)
		for(int i=upper.y-1; i>0; i--)
			map[i][0] = map[i-1][0];
		for(int j=0; j<c-1; j++)
			map[0][j] = map[0][j+1];
		for(int i=0; i<upper.y; i++)
			map[i][c-1] = map[i+1][c-1];
		for(int j=c-1; j>1; j--)
			map[upper.y][j] = map[upper.y][j-1];
		map[upper.y][1] = 0;

		// 공기 청정기 하단의 바람 (시계 방향)
		for(int i=lower.y+1; i<r-1; i++)
			map[i][0] = map[i+1][0];
		for(int j=0; j<c-1; j++)
			map[r-1][j] = map[r-1][j+1];
		for(int i=r-1; i>lower.y; i--)
			map[i][c-1] = map[i-1][c-1];
		for(int j=c-1; j>1; j--)
			map[lower.y][j] = map[lower.y][j-1];
		map[lower.y][1] = 0;
	}

	for(int i=0; i<r; i++)
		for(int j=0; j<c; j++)
			sum+=map[i][j];
	
	cout<<sum+2;

	return 0;
}

BOJ_미세먼지 안녕!