SW Expert Academy - 2382. 미생물 격리

문제링크

• 미생물 격리

문제설명

• N x N 크기의 구역 안에 K 개의 미생물 군집이 주어진다.
• 군집은 미생물의 수와 방향을 가지고 있으며 한 시간마다 이동방향에 있는 다음 셀로 이동한다.
• 구역의 가장 바깥쪽 가장자리에는 약품이 칠해져 있고, 약품이 칠해진 곳에 군집이 도달하면 미생물의 수가 절반으로 줄어든다. (홀수의 경우 2로 나눈 나머지는 버린다.)
  • 미생물 수가 0이 되면 군집은 사라진다.
• 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다.
  • 합쳐진 군집의 미생물 수는 군집들의 미생물 수의 합이며, 이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다. 합쳐지는 군집의 미생물 수가 같은 경우는 주어지지 않는다.
• M 시간 후 남아 있는 미생물 수의 총합을 구하라.

문제접근1

• 군집이 놓인 좌표에 대해서만 로직을 수행해야 한다. 모든 좌표에 대해서 탐색을 하게 되면 시간초과에 걸린다. 자료구조는 큐를 활용하여 큐에 방문해야 하는 군집의 정보를 담아두고 하나의 사이클을 수행한다.
• 주의해야할 점은 한 시간동안 군집이 동시에 움직인다는 점이다. 하나의 셀에 두 개 이상의 군집이 모이는 경우 미생물 수가 합쳐지게 되는데, 미생물 수가 가장 많은 군집의 이동 방향이 합쳐진 군집의 이동방향이 되어야 한다. 따라서, 먼저 움직인 군집에 의해 미생물 수가 업데이트 되면 로직 순서상 늦게 움직이는 군집은 군집 대 군집의 미생물 수 비교가 아닌 합쳐진 군집의 미생물 수와 비교하게 된다.
• 따라서, 별도의 배열을 두어 같은 셀에 위치하는 군집들 중 가장 미생물 수가 많은 군집의 이동방향을 기록할 수 있도록 하였다.
• 자료구조 set 을 활용하여 중복을 허용하지 않고, 군집이 위치하는 좌표 정보만을 담아두는 컨테이너를 활용하여 다음 사이클에 방문해야 하는 군집 정보를 큐에 업데이트 해준다.

구현1

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#include <set>
#define MAX_N 100
using namespace std;

typedef struct _cluster
{
	int xpos, ypos, dir, num;
} CLUSTER;

int N, M;
int dx[5] = { 0, -1, 1, 0, 0 };
int dy[5] = { 0, 0, 0, -1, 1 };

queue<CLUSTER> q;

int changeDirection(int cdir)
{
	if (cdir == 1) return 2;
	else if (cdir == 2) return 1;
	else if (cdir == 3) return 4;
	else if (cdir == 4) return 3;
}
bool moveNextCell(CLUSTER& curCluster)
{
	int nx = curCluster.xpos + dx[curCluster.dir];
	int ny = curCluster.ypos + dy[curCluster.dir];
	// 약품이 칠해진 셀에 도착하는 경우 군집 내 미생물의 절반이 죽는다.
	// 약품이 칠해진 셀에 두 개 이상의 군집이 모이는 경우는 없다.
	if (nx == 0 || nx == N - 1 || ny == 0 || ny == N - 1)
	{
		curCluster.num /= 2;
		// 군집이 사라지는 경우
		if (curCluster.num == 0) return false;
		curCluster.dir = changeDirection(curCluster.dir);
	}
	curCluster.xpos = nx;
	curCluster.ypos = ny;
	return true;
}

int solution()
{
	for (int time = 0; time < M; time++)
	{
		set<pair<int, int>> posTable; // 이동한 좌표들을 담는다. (중복 허용  x)
		int table[MAX_N][MAX_N][2];
		int nums[MAX_N][MAX_N]; // 해당 좌표에 도달한 군집 중 미생물 수가 가장 많은 경우를 담는다.
		memset(table, 0, sizeof(table));
		memset(nums, 0, sizeof(nums));
		while (!q.empty())
		{
			CLUSTER curCluster = q.front();
			q.pop();

			if (moveNextCell(curCluster))
			{
				posTable.insert(make_pair(curCluster.xpos, curCluster.ypos));
				table[curCluster.xpos][curCluster.ypos][0] += curCluster.num;
				// 군집이 합쳐지는 경우 군집들 중 미생물 수가 가장 많은 군집의 이동방향으로 설정한다.
				if (nums[curCluster.xpos][curCluster.ypos] < curCluster.num)
				{
					nums[curCluster.xpos][curCluster.ypos] = curCluster.num;
					table[curCluster.xpos][curCluster.ypos][1] = curCluster.dir;
				}
			}
		}

		// 큐를 다시 채우기
		for (auto ele : posTable)
		{
			CLUSTER nCluster;
			nCluster.xpos = ele.first;
			nCluster.ypos = ele.second;
			nCluster.num = table[ele.first][ele.second][0];
			nCluster.dir = table[ele.first][ele.second][1];
			q.push(nCluster);
		}
	}

	int ret = 0;
	while (!q.empty())
	{
		ret += q.front().num;
		q.pop();
	}
	return ret;
}

int main(int argc, char** argv)
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int test_case;
	int T;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		int K;
		cin >> N >> M >> K;
		int row, col, num, dir;
		for (int i = 0; i < K; i++) 
		{
			CLUSTER cluster;
			cin >> row >> col >> num >> dir;
			cluster.xpos = row;
			cluster.ypos = col;
			cluster.num = num;
			cluster.dir = dir;
			q.push(cluster);
		}
		int ans = solution();
		cout << "#" << test_case << " " << ans << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

문제접근2

• 미생물 수를 기준으로 군집 정보를 오름차순 정렬한다.
• 앞에서부터 군집을 차례대로 이동시킨다.
• 군집이 합쳐지는 경우 마지막에 해당 좌표로 이동한 군집이 미생물 수가 가장 많은 군집이므로 이때 결정된 방향이 합쳐진 군집의 방향이 된다.

구현2

#include <iostream>
#include <memory.h>
#include <vector>
#include <queue>>
#include <algorithm>

#define MAX_N 100
#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4
#define EMPTY 0
using namespace std;

typedef struct _data {
	int xpos;
	int ypos;
	int num;
	int dir;
} DATA;

int N, K, M;
int dx[5] = { 0, -1, 1, 0, 0 };
int dy[5] = { 0, 0, 0, -1, 1 };
vector<DATA> list;

bool cmp(DATA d1, DATA d2)
{
	return d1.num < d2.num; // 미생물 수 기준 오름차순 정렬
}

void init()
{
	list.clear();
}

void input()
{
	init();
	cin >> N >> M >> K;
	for (int i = 0; i < K; i++) {
		int xpos, ypos, num, dir;
		cin >> xpos >> ypos >> num >> dir;
		list.push_back({ xpos, ypos, num, dir });
	}
}

int getReverseDir(int dir)
{
	if (dir == UP) return DOWN;
	if (dir == DOWN) return UP;
	if (dir == LEFT) return RIGHT;
	if (dir == RIGHT) return LEFT;
}

int move()
{
	int ret = 0;
	pair<int, int> board[MAX_N][MAX_N];
	memset(board, 0, sizeof(board));

	sort(list.begin(), list.end(), cmp);
	for (auto ele : list) {
		int nx = ele.xpos + dx[ele.dir];
		int ny = ele.ypos + dy[ele.dir];
		if (nx == 0 || nx == N - 1 || ny == 0 || ny == N - 1) {
			board[nx][ny].first = ele.num / 2;
			board[nx][ny].second = getReverseDir(ele.dir);
			continue;
		}
		board[nx][ny].first += ele.num;
		board[nx][ny].second = ele.dir;
	}

	list.clear();
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (board[r][c].first == EMPTY) continue;
			list.push_back({ r, c, board[r][c].first, board[r][c].second });
			ret += board[r][c].first;
		}
	}


	return ret;
}

int moveProc()
{
	int ret = 0;
	for (int time = 1; time <= M; time++) {
		ret = move();
	}
	return ret;
}

void test()
{
	input();
	cout << moveProc() << endl;
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 0;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	// test();
	for (test_case = 1; test_case <= T; ++test_case)
	{
		input();
		cout << "#" << test_case << " " << moveProc() << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}