BOJ : 17144 미세먼지 안녕!

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

 

---

[BOJ 17144(G5) 리뷰]

골드5문제인데 왤케 어렵냐 ..

설명만 봤을땐 정말 간단해 보이는데 은근 구현하는게 까다로웠다.

문제를 풀때 주의해야 할 점은 미세먼지가 퍼질때 확산이 한번에 처리되어야 한다는점이다.

한번에 처리되지 않는다면 이전 칸에서 확산된 미세먼지가 다음 칸의 미세먼지를 확산할때 영향을 끼칠 수 있다.

이 문제를 해결하기 위해 나는 새로운 배열을 만들고 확산될 미세먼지 양을 따로 저장해놓은 뒤 나중에 합쳐 해결했다.

 

다음은 공기청정기의 위치에 따라 미세먼지의 위치를 이동시키는 작업이다.

이 작업이 굉장히 까다로웠다. 윗쪽 공기청정기는 반시계방향으로, 아래쪽 공기청정기는 시계방향으로 회전해야한다. 

처음엔 배열index를 이용하여 한칸씩 밀어주려고 했으나 끝에 다다르면 방향을 바꾸고 하는게 굉장히 복잡해보여 BFS를 이용했다. BFS를 이용하기 위해 wind라는 새로운 배열을 만들어 이동이 일어나는 칸에 대해 미리 1또는 2로 마킹을 해놓고 마킹된 위치에 대해서만 BFS를 수행하도록 하여 미세먼지의 이동과정을 구현했다.

 

결과적으로,

미세먼지의 확산을 처리하는 diffusion함수와 미세먼지의 이동을 위한 바람의 방향을 나타내기 위한 windset함수 그리고 미세먼지를 이동시키는 move함수를 구현했다.

 

diffusion과 move를 T번 수행한 후에 map에 있는 모든값을 더하는 값이 출력값이다.

 

위 로직대로 처리했지만 어쩌다보니 코드가 굉장히 지저분해져서 아마 다른사람이 내 코드를 보면 해석이 힘들거다 ..

 

---

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
#define X first
#define Y second


int R, C, T;
int map[51][51];
int check[51][51];
int wind[51][51];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
vector <pair<int, int>> air;
int ans = 0;

void move()
{
	for (int i = 0; i < R; i++)
		fill(check[i], check[i] + C, 0);

	queue <pair<int, int>>Q;
	auto start = air[0];
	start.Y += 1;
	check[start.X][start.Y] = 1;
	Q.push({ start.X,start.Y });
	int prev = 0;
	int nxt = 0;
	while (!Q.empty())
	{
		auto cur = Q.front(); Q.pop();
		nxt = map[cur.X][cur.Y];
		map[cur.X][cur.Y] = prev;
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
			if (wind[nx][ny] != 1 || check[nx][ny]) continue;
			Q.push({ nx,ny });
			check[nx][ny] = 1;
			prev = nxt;
		}
	}

	start = air[1];
	start.Y += 1;
	check[start.X][start.Y] = 1;
	Q.push({ start.X,start.Y });
	prev = 0;
	nxt = 0;
	while (!Q.empty())
	{
		auto cur = Q.front(); Q.pop();
		nxt = map[cur.X][cur.Y];
		map[cur.X][cur.Y] = prev;
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
			if (wind[nx][ny] != 2 || check[nx][ny]) continue;
			Q.push({ nx,ny });
			check[nx][ny] = 1;
			prev = nxt;
		}
	}
}

void diffusion()
{
	for (int i = 0; i < R; i++)
		fill(check[i], check[i] + C, 0);

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if (map[i][j] == 0 || map[i][j]==-1) continue;
			int cnt = 0;
			int val = map[i][j] / 5;
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = i + dx[dir];
				int ny = j + dy[dir];
				if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
				if (map[nx][ny] == -1) continue;
				check[nx][ny] += val;
				cnt++;
			}
			map[i][j] = map[i][j] - (val * cnt);
		}
	}

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			map[i][j] += check[i][j];
		}
	}

}

void windset()
{
	for (int i = 0; i < C; i++)
		wind[0][i] = 1;
	for (int i = 0; i < C; i++)
		wind[air[0].X][i] = 1;
	for (int i = 0; i < air[0].X; i++)
		wind[i][0] = 1;
	for (int i = 0; i < air[0].X; i++)
		wind[i][C - 1] = 1;

	for (int i = 0; i < C; i++)
		wind[air[1].X][i] = 2;
	for (int i = 0; i < C; i++)
		wind[R - 1][i] = 2;
	for (int i = air[1].X; i < R; i++)
		wind[i][0] = 2;
	for (int i = air[1].X; i < R; i++)
		wind[i][C - 1] = 2;

	wind[air[0].X][air[0].Y] = -1;
	wind[air[1].X][air[1].Y] = -1;
}

void count()
{
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			ans += map[i][j];
		}
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(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)
				air.push_back({ i,j });
		}
	}
	windset();
	while (T--)
	{
		diffusion();
		move();
	}
	
	count();
	cout << ans+2;

	
}