17144번 미세먼지 안녕

241113 풀이

#include <vector>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;


int r, c, t;
vector<vector<int>> v;

pair<int, int> upClean;
pair<int, int> downClean;

void Explosion()
{
	vector<vector<int>> vTemp(r, vector<int>(c));

	vector<pair<int, int>> dir
		= { {-1,0},{1,0},{0,-1},{0,1} };

	for (int i = 0; i < v.size(); ++i)
	{
		for (int j = 0; j < v[i].size(); ++j)
		{
			int namegi = v[i][j] / 5;

			// 상하좌우에 해당하는 공간에 더하게 한 다음에 

			// 6 + 5 // 임시변수를 만들어서 진행해야 한다. 
				// 넣으려는 값에 값이 있을 수 있다. 

			int cnt = 0;
			// 상하좌우로 확산하기 전에 
				// 범위체크 해야 한다.
			for (int k = 0; k < 4; ++k)
			{
				int nextY = i + dir[k].first;
				int nextX = j + dir[k].second;

				if (nextY < 0 || nextY >= r)
					continue;

				if (nextX < 0 || nextX >= c)
					continue;

				// 공기 청소기면 안된다! 
				if (v[nextY][nextX] == -1)
					continue;

				vTemp[nextY][nextX] += namegi;
				cnt++;
			}

			// 원본 계산해야 한다. 

			vTemp[i][j] += v[i][j] - cnt * namegi;

		}
	}

	v = vTemp;


	for (int i = 0; i < v.size(); ++i)
	{
		for (int j = 0; j < v[i].size(); ++j)
		{
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

// 열 : r / 행 : c
// 공기 청소기가 미세먼지를 이동시키는 시퀀스를 작성하자. 
void AirMove()
{
	vector<vector<int>> vTemp(r, vector<int>(c));
	// 위쪽 친구는 오른쪽 위 왼쪽 아래 로 이동하는 시퀀스다.
	// upClean;

	int upCurY = upClean.first;
	int upCurX = upClean.second;

	// 1. 오른쪽
	// [y][x] = [y][x - 1]
	for (int i = c - 1; i >= 0; --i)
	{
		if (v[upCurY][i] == -1)
			continue;
		vTemp[upCurY][i] = v[upCurY][i - 1];
	}

	// 2. 위쪽 이동.
	for (int i = 0; i < upCurY; ++i)
	{
		vTemp[i][c - 1] = v[i + 1][c - 1];
	}

	// 3. 왼쪽으로 이동
	for (int i = 0; i < r - 1; ++i)
	{
		vTemp[0][i] = v[0][i + 1];
	}

	// 4. 아래쪽으로 이동
	for (int i = upCurY - 1; i > 0; --i)
	{
		if (v[i][0] == -1)
			continue;
		vTemp[i][0] = v[i - 1][0];
	}


	// 아래쪽 친구는 오른쪽 아래쪽, 왼쪽, 위쪽. 으로 이동하는 시퀀스
	v = vTemp;

	for (int i = 0; i < v.size(); ++i)
	{
		for (int j = 0; j < v[i].size(); ++j)
		{
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
}



int main()
{
	
	cin >> r >> c >> t;
	v.resize(r, vector<int>(c));
	
	bool upDown = false;

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			cin >> v[i][j];

			if (v[i][j] == -1)
			{
				if (upDown == false)				
					upClean = make_pair(i, j);		
				else
					downClean = make_pair(i, j);
			}

		}
	}

	cout << endl;
	// 공기 청정기가 설치된 곳은 -1 , -1 이다. 
		// 위쪽인 부분과 오른쪽인 부분을 구별해야 한다.

	//for (int i = 0; i < r; ++i)
	//{
	//	for (int j = 0; j < c; ++j)
	//	{
	//		cout << v[i][j] << " ";
	//	}
	//	cout << endl;
	//}
	//cout << endl << endl;
	
	
	// 공기 청정기로 들어오는 미세먼지는 없어진다. 
	while (t > 0)
	{
		t--;
		// 확산하는 시퀀스 
		Explosion();


		// 청소기가 미세먼지를 이동시키는 시퀀스 
		AirMove();
	}

	//for (int i = 0; i < r; ++i)
	//{
	//	for (int j = 0; j < c; ++j)
	//	{
	//		cout << v[i][j] << " ";
	//	}
	//	cout << endl;
	//}
}

첫번째 코드

-> 1번 예제만 맞음...
-> 확산에서 잘못됨..

#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <queue>


// 반시계, 시계로 돌릴수있는 상하좌우를 설정해야 함.

// 반시계 우 , 상 , 좌 , 하 로 순환이동함.
// 1번이 반시계
int dy1[]{ 0,-1,0,1 };
int dx1[]{1,0,-1,0};


// 시계는 우 하 좌 상으로 이동함. 
int dy2[]{ 0,1,0,-1 };
int dx2[]{1,0,-1,0};


bool check = false;
vector<pair<int, int>>air1, air2;

int r, c, t;

// 반시계, 시계 방향으로 이동할 인덱스를 저장한 함수를 만들자. 
void MakeCircuit(int startY, int startX)
{
	// 방향을 결정할 변수
	int idx = 0;
	int nextY = startY;
	int nextX = startX;
	// true 일 때는 반시계로 처리 
	if (check)
	{
		// 언제 끝낼지를 알아야 함.
		while (1)
		{
			int tempY = nextY + dy1[idx];
			int tempX = nextX + dx1[idx];
			
			// 테두리에 걸리면 idx 증가하자.
			if (tempY >= r || tempY < 0
				|| tempX >= c || tempX < 0)
			{
				++idx;
			}
			else
			{
				air1.push_back(make_pair(tempY, tempX));
				nextY = tempY;
				nextX = tempX;
			}

			if (nextY == startY && nextX == startX)
			{
				air1.pop_back();
				break;
			}
		}		
	}
	// 여기는 시계 방향으로 순환해야 함.
	else
	{
		// 언제 끝낼지를 알아야 함.
		while (1)
		{
			int tempY = nextY + dy2[idx];
			int tempX = nextX + dx2[idx];

			// 테두리에 걸리면 idx 증가하자.
			if (tempY >= r || tempY < 0
				|| tempX >= c || tempX < 0)
			{
				++idx;
			}
			else
			{
				air2.push_back(make_pair(tempY, tempX));
				nextY = tempY;
				nextX = tempX;
			}

			if (nextY == startY && nextX == startX)
			{
				air2.pop_back();
				break;
			}
		}
	}
}

//확산 
void func(vector<vector<int>>&v)
{
	// 임시 값 있어야 함. 
	vector<vector<int>>temp(v);

	// 원소 하나하나씩 처리하는 것이므로, 큐로 돌리면 됨.
	// 큐를 bfs처럼 사용하는 것이 아니라
	// 유용하게 사용하도록 하자.

	queue<pair<int, int>>q;
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if(v[i][j] != -1 && v[i][j])
				q.push(make_pair(i, j));
		}
	}

	while (!q.empty())
	{
		int yy = q.front().first;
		int xx = q.front().second;
		q.pop();
		int value = v[yy][xx] / 5;

		// 4 방면 확인을 하는 것인데 , 기존에 만들어진 배열 사용하자.
		for (int i = 0; i < 4; ++i)
		{
			int nextY = yy + dy1[i];
			int nextX = xx + dx1[i];

			// 테두리 확인 및 공기 청소기 확인.
			if (nextY < 0 || nextY >= r
				|| nextX < 0 || nextX >= c
				|| v[nextY][nextX] == -1)
				continue;
			// 인접한 곳에 갈 값
			temp[nextY][nextX] += value;
			
			v[yy][xx] -= value;
		}
	}

	// 임시 변수 계속 가지고 있다가 나중에 처리
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			v[i][j] += temp[i][j];
		}
	}
	return;

}


// 공기 청정기로 이동시키자.
void go(vector<pair<int, int>> &v, vector<vector<int>> &v2) {
	for (int i = v.size() - 1; i > 0; i--) {
		v2[v[i].first][v[i].second] = v2[v[i - 1].first][v[i - 1].second];
	}
	v2[v[0].first][v[0].second] = 0;
	return;
}

//11:25
int main()
{		

	
	cin >> r >> c >> t;

	vector<vector<int>>v(r, vector<int>(c));

	

	
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			cin >> v[i][j];

			// 문제에서 공기 청정기가 몇개 들어오는지 
			// 설명 안되어 있음.
			if (v[i][j] == -1)
			{
				// 반시계 방향 인덱스 설정하기
				if (check == false)
				{
					//cout << "reverse" << "start : " << i << " " 
					//	<< j << endl;
					check = true;
					MakeCircuit(i, j);
					//cout << "hello" << endl;

					//for (auto iter : air1)
					//	cout << iter.first << " " << iter.second << endl;
				}
				// 시계 방향 인덱스 설정하기
				else
				{
					check = false;
					//cout << "origin" << "start : " << i << " "
					//	<< j << endl;
					MakeCircuit(i, j);
					//cout << "hello2" << endl;
					//for (auto iter : air2)
					//	cout << iter.first << " " << iter.second << endl;
				}
			}
		}
	}


	// 1. 미세 먼지 확산

	// 2. 공기청정기 날리기 

	// 3. t만큼의 반복 동작

	while (--t)
	{
		func(v);
		go(air1, v);
		go(air2, v);
	}

	int ret = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (v[i][j] != -1)
				ret += v[i][j];
		}
	}

	cout << ret;
}