[SW Expert Academy] 2382. 미생물 격리 C/C++ 풀이

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl&categoryId=AV597vbqAH0DFAVl&categoryType=CODE#none

SW Expert Academy

 

또다시 시뮬레이션 문제!

시뮬레이션 문제의 핵심은 문제를 얼마나 빨리 이해하느냐인듯...

집중해서 안보면 문제를 이해하는데에만 5-7분은 걸리는 것 같다.

 

우선 나의 풀이는

 

#include <cstdio>
#include <utility>
#include <vector>

using namespace std;

// type으로 저장해둠, 미생물의 위치(x, y), 미생물의 수, 미생물의 방향
typedef vector<pair<pair<int, int>, pair<int, int>>> germ_vector;
typedef pair<pair<int, int>, pair<int, int>> germ_type;

// testcase 확인을 위한 입력 설정
FILE* in = fopen("input.txt", "r");

int t;
int n;
int k;
int m;
//방향 설정, 0 -> 1, 1 -> 0, 2 -> 3, 3-> 2 로 이동해서 별도의 변환 배열도 만들었다.
int dir_x[4] = { -1, 1, 0, 0 };
int dir_y[4] = { 0, 0, -1, 1 };
int trans[4] = {1, 0, 3, 2};

int solution(int n, int m, int k, germ_vector& germ) {
	for (int g = 0; g < m; g++)
	{
    	// 한 곳에서 겹치는 경우 전체 미생물을 저장할 배열, 빠르게 찾을 수 있도록 하기 위해
        // 2차원 배열로 설정해 둠
		int delay[101][101] = {0 ,};
        // 미생물이 모두 없어지면 m 시간을 돌 필요 없음.
		if (germ.empty())
			break;
        // 미생물 처음부터 끝까지 순회
		for (int i = 0; i < germ.size(); i++)
		{
			int now_x = germ[i].first.first; int now_y = germ[i].first.second;
			int germ_num = germ[i].second.first; int now_dir = germ[i].second.second;
			//미생물 위치 이동
            now_x = now_x + dir_x[now_dir];
			now_y = now_y + dir_y[now_dir];
            //만약 벽이라면 미생물 절반, 방향 반대로
			if (now_x == 0 || now_y == 0 || now_x == n - 1 || now_y == n - 1)
			{
				germ_num = germ_num / 2;
				now_dir = trans[now_dir];
			}
            // 미생물 정보 갱신
			germ_type renew = make_pair(make_pair(now_x, now_y), make_pair(germ_num, now_dir));
			germ[i] = renew;
            // 앞선 미생물들 중에 겹치는 위치에 있는 것들을 탐색
			for (int j = 0; j < i; j++)
			{
				int tmp_x = germ[j].first.first; int tmp_y = germ[j].first.second;
                //겹칠 경우
				if (now_x == tmp_x && now_y == tmp_y)
				{
					int tmp_num = germ[j].second.first;
					int remove_idx;
					int new_num = germ_num + tmp_num;
                    // 미생물 숫자 비교, 작은 쪽의 미생물은 데이터를 삭제
					if (tmp_num > germ_num)
					{
						remove_idx = i;
					}
					else
					{
						remove_idx = j;
					}
                    // 2차원 배열에 이미 값이 있는지 살피고, 있다면 원래 값에다가 현재 미생물 수 추가
					if (delay[now_x][now_y] != 0)
					{
						delay[now_x][now_y] = delay[now_x][now_y] + germ_num;
					}
                    //아니라면 새로 만들어줌(현재 미생물 수, 겹치는 미생물 수)
					else
					{
						delay[now_x][now_y] = new_num;
					}
                    // 수가 작은 미생물 데이터는 삭제
					germ.erase(germ.begin() + remove_idx);
                    // 수가 모두 앞으로 당겨졌기 때문에 i는 증가하지 않도록 줄임
					i--;
                    // 다음 미생물으로 바로 이동
					break;
				}
			}
		}
        // 한 시간이 끝난 이후 2차원 배열의 값을 이용하여 전체 미생물 수 갱신
		for (int i = 0; i < germ.size(); i++)
		{
			int now_x = germ[i].first.first; int now_y = germ[i].first.second;
			if (delay[now_x][now_y] != 0)
				germ[i].second.first = delay[now_x][now_y];
		}
	}
    //미생물 데이터가 하나도 없다면 0
	if(germ.empty())
		return 0;
    // 아니라면 전체 순회하며 미생물 수 합을 구해줌
	else
	{
		int ans = 0;
		for (int i = 0; i < germ.size(); i++)
			ans = ans + germ[i].second.first;
		return ans;
	}
}

int main() {
	fscanf(in, "%d", &t);
	for (int i = 0; i < t; i++)
	{
		fscanf(in, "%d %d %d", &n, &m, &k);
		germ_vector germ;
		for (int j = 0; j < k; j++)
		{
			int a, b, c, d;
			fscanf(in, "%d %d %d %d", &a, &b, &c, &d);
			germ.push_back(make_pair(make_pair(a, b), make_pair(c, d - 1)));
		}
		printf("#%d %d\n", i + 1, solution(n, m, k, germ));
	}
}

 

구현에 애를 먹었던 부분은

 

최대 4방향에서 미생물이 합쳐질 수 있는데, 이때 가장 큰 수를 가진 미생물을 선정하고 그 전체 값을 저장하는 부분이다.

 

나는 이를 각각의 미생물의 데이터 갱신이 끝난 뒤, 앞선 미생물들의 위치 정보를 비교하여 겹칠 때마다 미생물 수가 큰 데이터만 남기고 나머지는 삭제하고 미생물의 합은 2차원 배열에 저장하는 방식으로 구현했다. 즉, 방향 값은 벡터에 남기고 전체 미생물의 합은 2차원 배열에 따로 저장한 것이다. 처음에는 미생물의 합 또한 벡터에다 구현했는데 탐색에 시간이 많이 들어 이차원 배열에 구현했다.