boj, 백준) 17144. 미세먼지 안녕! ( C / C++ )

1. 문제 링크

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

17144번: 미세먼지 안녕!

2. 문제 개요

 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

 공기청정기가 작동한다.

 

3. 문제 힌트

 퍼지는 것은 BFS처럼 Queue에 넣어서 1번만 해준다.

 

4. 문제 풀이

 이런 시뮬레이터 같은 문제는 어떻게 구현할지가 중요하다.

 퍼지는것을 바로 퍼뜨려서 맵에 적용시키면 다음 먼지와 충돌이 발생할 수 있다.

따라서 맵의 먼지를 모두 Queue에 담고 나서 맵을 초기화 한 후(새로운 맵이나,)에 저장해야 한다.

 

바람은 단순히 반복문을 사용해서 구현한다.

 

 

5. 코드

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

int r, c, t;
int map[50][50];
int ret;

struct COORD {
	int y, x;
	int val;
};

vector<COORD> cleaner;
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };

int main(void)
{
	scanf("%d %d %d", &r, &c, &t);

	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
		{
			scanf("%d", &map[i][j]);

			if (map[i][j] == -1)
			{
				COORD start;
				start.y = i, start.x = j, start.val = map[i][j];
				cleaner.push_back(start);
			}
			
		}

	while (t--)
	{
		queue<COORD>q;

		for (int i = 0; i < r; i++)
			for (int j = 0; j < c; j++)
			{
				if (map[i][j] != 0)
				{
					COORD target;
					target.y = i, target.x = j, target.val = map[i][j];
					q.push(target);
				}

			}
		while (!q.empty())
		{
			COORD cur = q.front(); q.pop();
			int num = 0;

			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];

				if (nx < 0 || ny < 0 || nx >= c || ny >= r || map[ny][nx] == -1)
					continue;

				//this point can spread
				num++;
				map[ny][nx] += cur.val / 5;
			}
			//my fine dust.
			map[cur.y][cur.x] -= (cur.val / 5)*num;
		}


		//moving
		//cleaner[0] -> upper
		//cleaner[1] -> lower
		COORD upper, lower;
		upper = cleaner[0], lower = cleaner[1];
		//upper side
		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++)
			ret += map[i][j];
	printf("%d", ret + 2);
	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~